In preparation for Christmas and a brand new year, your school is planning to host a fire drill to review the safety protocols in place.

You have decided to analyze the efficiency of the procedure by observing a particular hallway in the school. The hallway can be represented as a number line that is $N$ meters long, labelled from $1$ to $N$. There are $M$ fire exits at locations $p_i$ across the hallway, and they can be accessed from classrooms that are within $d_i$ meters of it. It is guaranteed that there is at most one exit located at any given location $p_i$. In the event that certain fire exits become too crowded, the school's front entrance (location at position $1$) and back door (located at position $N$) are deemed valid exits for any classroom in the school.

To ensure the drill goes smoothly, write a program that supports $Q$ of the following queries:

• 1 x: What is the position of the closest reachable exit from the class at position $x$? If there are multiple equidistant exits, output the one with the lowest $p_i$.
• 2 x: If the nearest exit to the class located at $x$ becomes too crowded, how many other valid exits can the class choose to take?

Constraints

For this problem, you will NOT be required to pass the sample cases in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

$3\le N\le 2\times {10}^5$

$1\le Q\le 2\times {10}^5$

$0\le M\le N-2$

$2\le p_i\le N-1$

$0\le d_i\le N-3$

For all queries, $2\le x\le N-1$.

Subtask 1 [15%]

$3\le N\le 2\times {10}^3$

$1\le Q\le 2\times {10}^3$

Subtask 2 [20%]

There are only type 1 queries.

Subtask 3 [20%]

There are only type 2 queries.

Subtask 4 [45%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, $N$ and $M$.

The next $M$ lines each contain two integers, $p_i$ and $d_i$.

The next line contains a single integer, $Q$.

The next $Q$ lines each contain a query.

Output Specification

For each query, output the answer on a new line.

Sample Input

9 3
5 2
6 1
8 0
3
1 4
1 3
2 4

Sample Output

5
1
2

Explanation of Sample

Query 1: The closest exit from the classroom at 4 is at location 5.

Query 2: From location 3, the front entrance and the exit at location 5 are both a distance of 2 away, but we output 1 because it has a lower $p_i$ value.

Query 3: The exits accessible from location 4 are at locations 1, 5 and 9. Since the closest exit at location 5 becomes too crowded, we are left with 2 exits remaining.