시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 2 2 2 100.000%

문제

You have $n$ black ants in your terrarium, and the $i$-th black ant lives at coordinate $(a_i, b_i)$.

Each day for the next $m$ days, you will buy a new ant for your terrarium. You are only buying white ants, and the $i$-th white ant that you are buying will live at coordinate $(x_i, y_i)$.

Each day, you feed some of your insects. If you feed an insect, the insect will not be hungry in that day. If the $i$-th white ant is hungry and the $j$-th black ant is hungry, and $x_i \geq a_j$ and $y_i \geq b_j$, they will fight. Find, for each day, the smallest number of ants to feed such that there are no fights.

입력

The first line contains one integer $n$ ($1 \leq n \leq 100\,000$): the number of black ants in your terrarium.

Each of the next $n$ lines contains the description of black ants. The $i$-th of them contain two integers, $a_i, b_i$ ($0 \leq a_i, b_i \leq 100\,000$).

The next line contains one integer $m$ ($1 \leq m \leq 100\,000$): the number of days in which you are going to buy new white ants.

Each of the next $m$ lines contains the description of white ants in the order you buy them, such that the $i$-th of them contains two integers, $x_i, y_i$ ($0 \leq x_i, y_i \leq 100\,000$).

Note that different ants can live at points with the same coordinates.

출력

Print $m$ integers, such that the $i$-th of them equals the smallest number of ants that you should feed to avoid fights among the black ants $1,2,\ldots,n$ and the white ants $1,2,\ldots,i$.

예제 입력 1

3
0 0
1 1
2 2
4
0 0
1 1
0 0
3 3

예제 출력 1

1
2
2
3