Tại một cuộc thi, để thử thách sự bền bỉ của các đội chơi, ban tổ chức đã xây dựng ~n~ cây cột bê tông trên một đường thẳng, đường thẳng được chia ra thành các điểm cách đều nhau và đánh tọa độ từ ~[0 \ldots \infty)~ với đơn vị chia là mét, cây cột thứ ~i~ ~(1 \le i \le n)~ có tọa độ ~x_i~ và chiều cao ~y_i~ mét. Giữa hai cột khác nhau có một sợi dây nối nếu đoạn thẳng với hai đầu mút là hai đỉnh cột không có điểm chung với bất kì cột nào ở giữa, lúc này người chơi có thể đu từ đỉnh cây cột này qua đỉnh cây cột khác bằng sợi dây đó (lưu ý: trường hợp một đỉnh cột bất kỳ vừa chạm tới sợi dây thì sợi dây cũng được coi là đã bị vướng bởi đỉnh cột đó). Giả sử số lượng và độ dài của các sợi dây là vô hạn.

Tham gia thử thách này có ~m~ đội chơi lần lượt tham gia thử sức, mỗi đội chơi gồm ~2~ thành viên. Ban đầu, ~2~ thành viên của đội chơi thứ ~j~ ~(1 \le j \le m)~ đứng ở cây cột có vị trí ~a_j~ và ~b_j~. Các thành viên sẽ di chuyển theo quy luật:

• Nếu hai thành viên đang đứng ở cùng một cột, cả hai sẽ dừng lại.
• Còn không, người chơi đứng ở cột có tọa độ nhỏ hơn sẽ di chuyển sang cây cột khác thỏa mãn đồng thời: (1) cây cột di chuyển tới có thể di chuyển từ cột đang đứng bằng sợi dây nối 2 đỉnh cột đó, (2) cây cột di chuyển tới có tọa độ lớn hơn cây cột đang đứng, (3) cây cột có thể di chuyển tới có tọa độ lớn nhất có thể.

Yêu cầu:

Với mỗi đội chơi, hãy xác định vị trí cây cột mà ~2~ thành viên của mỗi đội chơi gặp nhau. Lưu ý vị trí cây cột ở đây được hiểu là số thứ tự của cây cột đó trong ~n~ cột ban đầu (đếm từ ~1~ tới ~n~ từ trái qua phải).

Dữ liệu:

Nhập từ bàn phím gồm:

• Dòng đầu tiên gồm ~1~ số nguyên ~n~ ~(1 \le n \le 10^5)~ là số lượng cây cột mà ban tổ chức đã xây dựng.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~x_i, y_i~ ~(1 \le x_i \le 10^7, 1 \le y_i \le 10^{11})~ là tọa độ và chiều cao của cây cột thứ ~i~ ~(1 \le i \le n)~. Dữ liệu được liệt kê theo thứ tự tăng dần theo tọa độ của các cây cột và đảm bảo rằng không có ~2~ cây cột nào ở cùng ~1~ tọa độ.
• Dòng thứ ~n + 1~ gồm ~1~ số nguyên ~m~ ~(1 \le m \le 10^5)~, số đội chơi tham gia thử thách.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~a_j~ và ~b_j~ ~(1 \le a_j, b_j \le n)~ là vị trí cây cột của ~2~ thành viên của đội chơi thứ ~j~ ~(1 \le j \le m)~ đang đứng.

Kết quả:

In ra màn hình ~1~ dòng duy nhất gồm ~m~ số nguyên, số thứ ~j~ là vị trí của cây cột mà ~2~ thành viên của đội chơi thứ ~j~ gặp nhau.

Sample Input

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

Sample Output

3 5 6 4

Giải thích:

Hình trên minh họa cho bộ dữ liệu ví dụ, với các mũi tên thể hiện cột mà người chơi sẽ di chuyển tới nếu đang đứng ở cột hiện tại.

Với đội chơi thứ ~3~, để đi từ cột ~1~ tới cột ~6~, người chơi thứ hai phải đi qua những cột sau: ~1 → 3 → 4 → 5 → 6~.

Chú ý rằng từ cột thứ ~4~ không thể di chuyển trực tiếp đến cột thứ ~6~, do cột thứ ~5~ sẽ vừa chạm tới sợi dây nối hai cột này.

Ràng buộc:

• ~20\%~ số điểm của bài tương ứng với các test có ~1 \le n \le 10^2, 1 \le m \le 10^2~.
• ~30\%~ số điểm khác của bài tương ứng với các test có ~1 \le n \le 10^3, 1 \le m \le 10^3~.
• ~50\%~ số điểm còn lại của bài tương ứng với các test có ~1 \le n \le 10^5, 1 \le m \le 10^5~.