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.