Cho ~n~ phần tử dưới dạng đoạn ~s_i=[l_i,r_i]~ và ~q~ truy vấn. Mỗi truy vấn bao gồm hai số nguyên ~a~ và ~b~, yêu cầu chia đoạn phần tử ~[s_a,s_{a+1},...,s_b]~ thành ít đoạn con liên tiếp nhất có thể sao cho mỗi phần tử chỉ thuộc đúng một đoạn và các phần tử trong cùng một đoạn đều không giao nhau.

Hai đoạn ~[l_x,r_x]~ và ~[l_y,r_y]~ được gọi là giao nhau nếu tồn tại ít nhất một giá trị ~z~ thỏa mãn đồng thời ~l_x \le z \le r_x~ và ~l_y \le z \le r_y~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 2.10^5)~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~l_i~ và ~r_i~ ~(1 \le l_i \le r_i \le 10^9)~.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \le q \le 2.10^5)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a~ và ~b~ ~(1 \le a \le b \le n)~ mô tả truy vấn.

Samples

Sample Input 1

2
1 1
1 1
3
1 1
2 2
1 2

Sample Output 1

1
1
2

Sample Input 2

3
1 1
2 2
3 3
3
1 1
2 3
1 3

Sample Output 2

1
1
1

Sample Input 3

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

Sample Output 3

3
1
3

Scoring

• Subtask ~1~ với ~20\%~ số điểm: ~q=1;\;a=b=1~
• Subtask ~2~ với ~20\%~ số điểm: ~n,q \le 5000~
• Subtask ~3~ với ~20\%~ số điểm: ~n \le 5000~
• Subtask ~4~ với ~20\%~ số điểm: ~n \le 2.10^5; \; q \le 100~
• Subtask ~5~ với ~20\%~ số điểm: Không còn ràng buộc gì thêm

Clarification

Trong ví dụ thứ ba,

• Ở truy vấn đầu tiên, chia đoạn các phần tử ~[1,4]~ thành ba đoạn ~[1,1]~, ~[2,3]~ và ~[4,4]~. Lưu ý rằng hai phần tử ~1~ và ~2~ không thể thuộc cùng một đoạn do hai đoạn ~[1,3]~ và ~[3,3]~ giao nhau.
• Ở truy vấn thứ hai, đoạn các phần tử ~[3,5]~ thỏa mãn không có hai phần tử nào giao nhau.