During a live set, a DJ uses an echo pedal that replays a note by jumping forward in time. The song is split into ~n~ notes. Note ~i~ lasts for ~d_i~ milliseconds. Its start time is

$$\displaystyle {\rm start}_1 = 0, \quad {\rm start}_{i+1} = {\rm start}_i + d_i. $$

The pedal is configured with a delay ~t_i~ for each note. If the pedal triggers on note ~i~, it jumps to the first note whose start time is strictly greater than ~\text{start}_i + t_i~. If no such note exists, the pedal lands in silence, and all further jumps stay in silence.

You are given many queries. Each query gives a starting note ~s~ and a number of jumps ~k~. For each query, output the note index where the echo lands after exactly ~k~ jumps, or ~0~ if it ends in silence.

Input

The first line contains two integers ~n~ and ~q~ (~1 \le n,q \le 2\times 10^5~), the number of notes and the number of queries.

The next ~n~ lines each contain two integers ~d_i~ and ~t_i~ (~1 \le d_i, t_i \le 10^9~), the duration and echo delay for each note.

The next ~q~ lines each contain two integers ~s~ and ~k~ (~1 \le s \le n~, ~0 \le k \le 10^{18}~), the starting note and number of jumps for each query.

Output

For each query, print a single integer: the note index after ~k~ jumps, or ~0~ if the echo is in silence.

Notes

Try selecting PyPy3 for your Python submissions for a free speed boost!

Examples

Input 1

5 5
3 4
2 3
4 1
1 7
5 2
1 1
1 2
1 3
2 1
3 2

Output 1

3
4
0
4
0

The start times are ~[0, 3, 5, 9, 10]~.

• From note 1, ~0 + 4 = 4~, so the next note is 3.
• From note 1, two jumps go ~1 \to 3 \to 4~.
• From note 1, three jumps go ~1 \to 3 \to 4 \to 0~.

Input 2

1 4
5 10
1 0
1 1
1 2
1 10

Output 2

1
0
0
0

The only note starts at time 0. Any positive jump exceeds all note start times, so the echo goes to silence.

Input 3

3 5
3 3
3 1
3 1
1 1
1 2
2 1
2 2
3 1

Output 3

3
0
3
0
0

The start times are ~[0, 3, 6]~. From note 1, ~0 + 3~ hits time ~3~ exactly, so the next note is ~3~ (strictly greater than ~3~).