Trên hệ trục tọa độ vuông góc ~Oxy~, cho tọa độ ~N~ điểm trong đó không có ba điểm nào thẳng hàng.

Yêu cầu: Tìm hai điểm trong ~N~ điểm để đường thẳng chứa hai điểm đó chia ~N-2~ điểm còn lại thành hai phần sao cho tổng số điểm của mỗi phần chênh lệnh nhau không quá ~1~.

Dữ liệu vào từ tệp văn bản DIVPOINT.INP:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 10^5)~ là số lượng điểm;
• ~N~ dòng sau, mỗi dòng chứa hai số nguyên ~x, y~ là toạ độ của một điểm ~(|x| ≤ 10^9~; ~\ |y| ≤ 10^9)~.

Kết quả ghi ra tệp văn bản DIVPOINT.OUT:

Một dòng gồm bốn số nguyên là toạ độ của hai điểm thoả mãn. Có thể có nhiều kết quả, ghi ra một kết quả bất kì.

Ràng buộc

• Có ~30\%~ số test ứng với ~N ≤ 100~;
• ~30\%~ số test khác ứng với ~N ≤ 5000~;
• ~40\%~ số test còn lại ứng với ~N ≤ 10^5~.

Ví dụ

Input

4
0 0
0 1
1 1
1 0

Output

0 0 1 1

Trên trục ~Ox~, cho ~N~ đoạn thẳng được đánh số từ ~1~ tới ~N~, đoạn thẳng thứ ~i~ ~(1 ≤ i ≤ N)~ nối điểm có tọa độ nguyên ~x = a_i~ và điểm có tọa độ nguyên ~x = b_i~ ~(a_i < b_i)~. Một điểm được gọi là thuộc đoạn thẳng thứ ~i~ nếu tọa độ của nó nằm trong đoạn ~[a_i, b_i]~.

Yêu cầu: Cho biết ~N~ đoạn thẳng và một số nguyên dương ~K~. Hãy viết một chương trình trả lời ~Q~ truy vấn. Ở truy vấn thứ ~j~ ~(1 ≤ j ≤ Q)~, khi cho biết hai số nguyên ~c_j~ và ~d_j~, bạn cần xác định giá trị ~L~ lớn nhất sao cho tồn tại hai số nguyên ~u, v~ thỏa mãn:

• ~c_j ≤ u < v ≤ d_j~ và ~v − u = L~;
• Tồn tại không quá ~K~ đoạn thẳng trong số ~N~ đoạn thẳng được cho sao cho mọi điểm ~x~ có tọa độ nguyên trong đoạn ~[u, v]~ đều thuộc ít nhất một trong các đoạn thẳng đó.

Nếu không tồn tại ~u, v~ nào thì ~L = 0~.

Dữ liệu vào từ tệp văn bản SEGMENT.INP:

• Dòng đầu tiên chứa ba số nguyên dương ~N,Q,K~ ~(1 ≤ K ≤ N ≤ 10^5, \ 1 ≤ Q ≤ 10^5)~;
• ~N~ dòng tiếp theo, dòng thứ ~i~ ~(1 ≤ i ≤ N)~ chứa hai số nguyên ~a_i~ và ~b_i~ ~(0 ≤ a_i < b_i ≤ 10^9)~;
• ~Q~ dòng cuối cùng, dòng thứ ~j~ ~(1 ≤ j ≤ Q)~ chứa hai số nguyên ~c_j~ và ~d_j~ ~(0 ≤ c_j < d_j ≤ 10^9)~.

Kết quả ghi ra tệp văn bản SEGMENT.OUT:

Gồm ~Q~ dòng, dòng thứ ~j~ ~(1 ≤ j ≤ Q)~ là giá trị ~L~ lớn nhất cho truy vấn thứ ~j~.

Ràng buộc

• Có ~20\%~ số test ứng với ~K = 1~; ~\ N,Q ≤ 2000~;
• ~20\%~ số test khác ứng với ~K = 1~;
• ~20\%~ số test khác ứng với ~K = 2~;
• ~20\%~ số test khác ứng với ~K ≤ 30~;
• ~20\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

3 4 1
6 8
1 5
4 6
1 10
2 6
4 7
5 9

Output

4
3
2
2

Giải thích

• Truy vấn ~1~: chọn ~[u, v] = [1, 5]~.
• Truy vấn ~2~: chọn ~[u, v] = [2, 5]~.
• Truy vấn ~3~: chọn ~[u, v] = [4, 6]~.
• Truy vấn ~4~: chọn ~[u, v] = [6, 8]~.

Input

4 3 2
2 5
6 8
9 11
8 10
1 8
6 11
8 11

Output

3
4
3

Giải thích

• Truy vấn ~1~: chọn ~[u, v] = [2, 5]~.
• Truy vấn ~2~: chọn ~[u, v] = [6, 10]~.
• Truy vấn ~3~: chọn ~[u, v] = [8, 11]~.

Trong giờ sinh hoạt lớp, cô giáo tổ chức cho các bạn học sinh chơi một trò chơi "Tô màu dãy ô vuông". Ban đầu, cô giáo chuẩn bị một dãy các ô vuông xếp cạnh nhau và được đánh số từ ~1~ đến ~N~ và được tô toàn bộ màu có số hiệu là ~0~. Trò chơi diễn ra trong ~M~ lượt chơi, mỗi lượt cô gọi một học sinh bất kì lên tô màu dải ô vuông: học sinh sẽ nghĩ ra ba số nguyên dương ~L, R, C~ ~(L ≤ R)~ và thực hiện tô màu có số hiệu ~C~ từ ô ~L~ đến ô ~R~ (màu của ô vuông sẽ là màu của người tô sau). Kết thúc ~M~ lượt chơi rất hăng say, được một dãy ô vuông rất đẹp, cô giáo bảo các bạn ghi lại ba số ~L, R, C~ mà các bạn nghĩ ra ở lượt chơi của mình và cô giáo đánh số lại các lượt chơi từ ~1~ đến ~M~. Sau đó, cô giáo đố các bạn một câu hỏi rất hóc búa: từ danh sách ghi thông tin tô màu của các bạn học sinh, hãy đưa ra thứ tự các lượt tô màu để từ dãy ô vuông ban đầu thu được dãy ô vuông khi trò chơi kết thúc.

Yêu cầu: Hãy giúp các bạn học sinh sắp xếp lại thứ tự các lượt tô màu.

Dữ liệu vào từ tệp văn bản COLOR.INP:

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ ~(1 ≤ N, M ≤ 5 \times 10^5)~ là số ô vuông và số lượt tô màu~;~
• ~M~ dòng sau, mỗi dòng thứ ~i~ chứa ba số nguyên ~L_i, R_i, C_i~ ~(1 ≤ i ≤ M;~ ~\ 1 ≤ L_i ≤ R_i ≤ N;~ ~\ 1 ≤ C_i ≤ 5 \times 10^5)~ mô tả dòng thứ ~i~ ở danh sách ghi thông tin một lượt lượt tô màu~;~
• Dòng cuối cùng chứa ~N~ số nguyên là số hiệu màu của từng ô vuông sau khi các bạn đã tô màu.

Kết quả ghi ra tệp văn bản COLOR.OUT:

Một dòng gồm ~M~ số nguyên là thứ tự tô màu để thu được dãy ô vuông khi trò chơi kết thúc. Có thể có bạn ghi nhầm thông tin lượt tô màu của mình nên không tìm được cách chọn thì in ra ~−1~. Nếu có nhiều cách chọn thì in ra cách bất kì.

Ràng buộc

• Có ~20\%~ số test ứng với ~1 ≤ N, M ≤ 9;~
• ~20\%~ số test khác ứng với ~1 ≤ N, M ≤ 5000~ và màu của mỗi lần tô là khác nhau~;~
• ~20\%~ số test khác ứng với ~1 ≤ N, M ≤ 5 \times 10^5~ và màu của mỗi lần tô là khác nhau~;~
• ~20\%~ số test khác ứng với ~1 ≤ N, M ≤ 5000;~
• ~10\%~ số test khác ứng với ~1 ≤ N, M ≤ 5 \times 10^5~ và ~1 ≤ C_i ≤ 5;~
• ~10\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

6 5
3 5 5
1 1 6
1 3 2
1 4 7
4 6 6
6 2 5 5 5 6

Output

4 5 3 1 2