There are $n$ black ants on a 2D plane.
Over the following period, $m$ white ants will arrive one after another. However, black ants and white ants will fight, and Xiao H does not want to see this happen.
Xiao H can feed an ant, which will make it lose the desire to fight. If a black ant at $(x, y)$ and a white ant at $(x', y')$ satisfy $x \leq x'$ and $y \leq y'$, and neither of them has been fed, they will fight.
Xiao H wants to know, after each white ant arrives, what is the minimum number of ants he needs to feed so that no ants will fight.
Note that Xiao H does not actually feed the ants; every time he performs a calculation, all ants are hungry.
Input
The first line contains an integer $n$, representing the number of black ants.
The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th black ant.
The next line contains an integer $m$, representing the number of operations.
The next $m$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th white ant that arrives.
Output
Output $m$ lines, each containing an integer representing the answer after the $i$-th white ant arrives.
Examples
Input 1
3 1 1 2 2 3 3 4 1 1 2 2 1 1 4 4
Output 1
1 2 2 3
Examples 2, 3, 4
See attachment for download.
Constraints
| Test Case ID | $n, m \leq$ | Special Property |
|---|---|---|
| $1 \sim 3$ | $50$ | None |
| $4 \sim 8$ | $1000$ | |
| $9 \sim 11$ | $100000$ | All points satisfy $x_i = y_i$ |
| $12 \sim 20$ | None |
For all data, it is guaranteed that $1 \leq n, m \leq 100000$ and $0 \leq x_i, y_i \leq 10^9$.