Hazel's Harvest

Hazel is starting a tree plantation. She likes to plan ahead and has prepared a planting schedule for $N$ trees.

The trees will be grown elsewhere before being moved to Hazel’s plantation. Each tree will be planted there in a specific year $Y$, when it will already be $H$ meters tall. Once planted, it remains in the plantation and grows exactly one meter per year. Thus, in any year $t \ge Y$, the tree is $H + t - Y$ meters tall.

To plan her future sales, Hazel considers $Q$ potential purchase orders for trees. Each order requests $K$ trees, each at least $V$ meters tall. An order can be fulfilled in a given year if the plantation has at least $K$ planted trees that are each at least $V$ meters tall.

The orders are independent: no trees are actually removed from the plantation, and each order is considered as if it were the only one. For each order, determine the earliest year in which it could be fulfilled.

Input

The first line contains an integer $N$ ($1 \le N \le 2 \times 10^{5}$) representing the number of trees in the planting schedule.

Each of the next $N$ lines describes a tree with two integers $Y$ and $H$ ($1 \le Y, H \le 10^{9}$), indicating respectively its planting year and its height in meters when planted.

The next line contains an integer $Q$ ($1 \le Q \le 2 \times 10^{5}$) representing the number of purchase orders.

Each of the next $Q$ lines describes a purchase order with two integers $K$ ($1 \le K \le N$) and $V$ ($1 \le V \le 10^{18}$), indicating respectively the number of trees requested and their minimum height in meters.

Output

For each purchase order in the input, output a line with an integer indicating the earliest year in which it could be fulfilled. It can be shown that an answer exists for each purchase order.

3
1 5
6 10
3 2
3
2 4
1 11
3 1

5
7
6

2
5 8
5 8
3
2 8
1 10
1 8

5
7
5