Tyler is a competitive rocket racer. Unlike in normal foot racing, rocket racers use their own collection of rockets to move instead of their feet. Tyler's collection consists of $N$ single-use rockets. The $i$-th rocket propels him $a_i$ meters forwards, but sends him $b_i$ meters backwards immediately after. Of course, rocket technology is constantly evolving, and racers need to update their collection frequently to ensure optimal performance. As Tyler's coach, you must handle $Q$ of the following events, each starting with a value $t_j$:

• If $t_j=0$ then an integer $r_j$ follows, and you must tell Tyler the minimum number of rockets he needs to complete an $r_j$ meter race. Note that the race is completed if Tyler reaches or passes the finish line at the $r_j$ meter mark at any point. Also, all rockets may only be used in the forward direction (i.e. initially towards the finish line).
• If $t_j>0$ then two integers $x_j$ and $y_j$ follow, indicating that Tyler replaces the $t_j$-th rocket with one that propels him $x_j$ meters forwards but sends him $y_j$ meters backwards immediately after.

Constraints

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

$1\le a_i,b_i,r_j,x_j,y_j\le {10}^9$

$0\le t_j\le N$

Subtask 1 [25%]

$1\le N,Q\le 3\times {10}^3$

Subtask 2 [25%]

$t_j=0$

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains an integer $N$.

The next $N$ lines each contain $2$ integers $a_i$ and $b_i$.

The next line contains an integer $Q$.

The next $Q$ lines each contain the description of an event on a single line, as described in the statement.

Output Specification

For each event with $t_j=0$ output the answer on its own line, or $-1$ if it is impossible to complete that race.

Sample Input

10
2 1
5 7
4 1
5 4
7 3
9 4
1 6
6 4
5 2
4 5
6
0 15
0 8
6 7 5
0 11
0 8
0 100

Sample Output

3
1
2
2
-1

Explanation

For the first event, Tyler should use his $5$-th, $6$-th, and $8$-th rockets in that order. This reaches a maximum forward distance of $15$ meters, which is just enough to complete the race.

For the fifth event, Tyler should use his $5$-th rocket and then his $2$-nd rocket. This reaches a maximum forward distance of $9$ meters, enough to complete the race.

For the sixth event, it is impossible for Tyler to complete the race regardless of which rockets he chooses to use.