H. Luxor Stairway
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After the ICPC World Finals in Luxor, the team Exceso de Chilaquiles explored the Mortuary Temple of Hatshepsut. Wandering through the ancient ruins, they discovered a mysterious stairway hidden beneath the temple.

The stairway contains $$$N+10^{18}+1$$$ steps numbered from $$$-10^{18}$$$ to $$$N$$$ from the lowest step to the highest one. The non-positive steps are underground, and the positive ones are over the surface.

Step $$$i$$$ is carved with an ancient integer $$$a_i$$$. According to the inscriptions, the integer of every step points to a lower step where the stone is more stable. For this reason, from step $$$i$$$ you are forced to jump to step $$$a_i$$$, where $$$a_i \lt i$$$.

The stairway is unstable. Every time someone jumps from a step, the stone cracks slightly, reducing its written integer by a value $$$k$$$. The value of $$$k$$$ may vary over time. More formally, after jumping from step $$$i$$$, the value of $$$a_i$$$ is reduced by a given value $$$k$$$.

The team has $$$Q$$$ plans to walk the stairway. During each plan, they will start at the step $$$s$$$ and jump through multiple steps until reaching a step $$$i$$$ such that $$$i \leq 0$$$ (they don't want to go too far underground). The team knows the value of $$$k$$$ for each of their plans.

The team is mentally exhausted from solving the problems of the contest, so they need your help to find the number of the step where they arrive at for each plan.

Note that all changes applied to the values $$$a_i$$$ during a plan remain for all subsequent plans.

Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 2 \cdot 10^5$$$)  — the number of steps over the surface and the number of plans.

The second line contains $$$N$$$ integers $$$a_1,a_2,\dots,a_N$$$ ($$$0 \leq a_i \lt i$$$)  — the integer written on the steps over the surface.

The following $$$Q$$$ lines contain the descriptions of the plans. Each of these lines contains two integers $$$s$$$ and $$$k$$$ ($$$1 \leq s \leq N$$$ and $$$1 \leq k \leq 10^9$$$)  — the description of each plan.

Output

For each plan, output the number of the step where the team Exceso de Chilaquiles stops.

Examples
Input
5 5
0 1 2 1 0
3 5
3 1
2 3
2 1
5 1
Output
0
-3
-4
-7
0
Input
3 4
0 1 2
3 2
1 4
2 3
2 5
Output
0
-2
-1
-4
Input
1 5
0
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000
Output
0
-1000000000
-2000000000
-3000000000
-4000000000