Bouncy Devices Game

Lostmonkey invented a super-bouncy device to impress his sheep friends. He laid out \(n\) devices in a straight line, and each device \(i\) has an initial bounce coefficient \(k_i\) (a positive integer). When a sheep reaches the \(i\)th device, it is bounced forward by \(k_i\) steps, landing on the device \(i+k_i\). If the device \(i+k_i\) does not exist, the sheep is blasted out.

The sheep is curious: if it starts from the \(i\)th device, how many bounces will it undergo before being blasted out? Meanwhile, Lostmonkey can modify the bounce coefficient of any device at any time (again, the coefficient must remain a positive integer).

You are given the initial setup and a series of operations. Each operation is one of the following:

• Update operation: Modify the bounce coefficient of a given device.
• Query operation: Given a starting device, determine the number of bounces before the sheep is blasted out.

The process for a query is as follows: starting at device \(i\), repeatedly move to device \(i+k_i\) and count each bounce until the next device does not exist. Print the count for that query.

inputFormat

The first line contains two integers \(n\) and \(q\) (\(1 \leq n, q \leq 10^5\)), representing the number of devices and the number of operations respectively.

The second line contains \(n\) integers \(k_1, k_2, \ldots, k_n\) (each \(k_i\) is a positive integer), which are the initial bounce coefficients of the devices.

The next \(q\) lines represent operations. Each operation is given in one of the following formats:

• 1 i x: Update the bounce coefficient of device \(i\) to \(x\).
• 2 i: Query the number of bounces before being blasted out when starting from device \(i\).

outputFormat

For each query operation (operations starting with 2), output the number of bounces on a new line.

sample

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

3
1
3