Lostmonkey has invented a super-bouncing device. To show off in front of his sheep friends, he invites a little sheep to play a game. At the beginning of the game, Lostmonkey places $n$ bouncing devices in a straight line on the ground, numbered from $0$ to $n-1$ in order. For each $0 \le i \le n-1$, an initial bounce coefficient $k_i$ is set for the $i$-th device. When the sheep lands on the $i$-th device, it will be bounced $k_i$ steps forward, landing on the $i+k_i$-th device. If the $i+k_i$-th device does not exist, the sheep is bounced off the line. The sheep wants to know: starting from the $i$-th device, how many times will it be bounced (including the final bounce off the line) before it is bounced off? To make the game more interesting, Lostmonkey can also modify the bounce coefficient of any device, but the bounce coefficient must always be a positive integer.

Input

The first line of the input contains an integer $n$, representing the $n$ bouncing devices placed on the ground. The second line contains $n$ space-separated positive integers $k_0, k_1, \ldots, k_{n-1}$, representing the initial bounce coefficients of the $n$ devices. The third line contains a positive integer $m$, representing the number of subsequent operations. Each of the following $m$ lines contains at least two space-separated integers $i$ and $j$. If $i=1$, you must output how many times the sheep will be bounced before it is bounced off, starting from the $j$-th device. If $i=2$, the line will contain three space-separated integers $i, j$, and $k$, indicating that the bounce coefficient of the $j$-th device is modified to $k$.

The input data guarantees that 20% of the data satisfies $n, m \le 10\,000$. 100% of the data satisfies $n \le 200\,000$ and $m \le 100\,000$.

Output

The number of lines in the output is equal to the number of lines where $i=1$ in the last $m$ lines of the input.

For the $h$-th query, output an integer representing the number of bounces calculated based on the bounce coefficients of the $n$ devices at that time.

Examples

Input 1

4
1 2 1 1
3
1 1
2 1 1
1 1

Output 1

2
3