Given $n$ black points on a plane, perform $m$ operations, where each operation adds one white point.

After each addition, you need to find the minimum number of black and white points to remove such that there is no black point $(x, y)$ and white point $(x', y')$ satisfying $x \leq x'$ and $y \leq y'$.

Input

The first line contains an integer $n$, representing the number of black points.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th black point.

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 white point added in the $i$-th operation.

Output

Output $m$ lines, each containing an integer representing the answer after the $i$-th operation.

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

Subtasks

For all data, it is guaranteed that $1 \leq n, m \leq 100000$ and $1 \leq x_i, y_i \leq 10^9$.