A. Trampolines
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$n$$$ trampolines are placed in a row and numbered $$$1$$$ through $$$n$$$ from left to right.

Each trampoline $$$i \ (1 \le i \le n)$$$ has a strength $$$t[i] \ (t$$$ is an array of length $$$n$$$).

If one throws a ball on trampoline $$$i$$$, it bounces immediately to the position $$$i + t[i]$$$ and the process repeats from this position to later positions (i.e., from the position $$$j = i + t[i]$$$, it bounces to position $$$j + t[j]$$$) until the ball exits the row, i.e., its position is strictly greater than $$$n$$$ for a given time.

You are given $$$q$$$ queries of two types :

  • Query of type $$$0$$$ : given two integers $$$i$$$ and $$$x$$$, set $$$t[i]$$$ to $$$x$$$ (i.e., $$$t[i] := x)$$$.
  • Query of type $$$1$$$ : starting at position $$$i$$$, output the last position the ball was in before exiting the row and the number of bounces it does before exiting the row (in this order).
Input

The first line: you are given two space separated integers $$$n, q$$$ $$$(1 \le n, q \le 10^5)$$$.

The second line: you will be given $$$n$$$ space separated integers, the array $$$(1 \le t[i] \le 10^5)$$$.

Then $$$q$$$ queries, each query starts with $$$t \in \{0, 1 \}$$$, the type of the query.

Each query of type $$$0$$$ is described by two integers $$$i (1\le i \le n)$$$ and $$$x (1 \le x \le 10^5)$$$. Queries of type $$$1$$$ are described by one integer $$$i (1 \le i \le n)$$$ as described in the statement.

Output

For each query of the second type, output two space separated integers : the last position the ball was in before exiting the row and the number of bounces it does before exiting the row $$$\textbf{(in this order)}$$$.

Scoring

subtaskconstraintsscoring
$$$1$$$$$$1 \le n, q \le 10000$$$$$$5$$$ pts
$$$2$$$there are no queries of type $$$0$$$$$$10$$$ pts
$$$3$$$No additional constraints$$$85$$$ pts

Example
Input
3 3
1 3 2
1 1
0 1 2
1 1
Output
2 2
3 2