The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Beta Round 13 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dsu

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Holes

time limit per test

1 secondmemory limit per test

64 megabytesinput

standard inputoutput

standard outputLittle Petya likes to play a lot. Most of all he likes to play a game «Holes». This is a game for one person with following rules:

There are *N* holes located in a single row and numbered from left to right with numbers from 1 to *N*. Each hole has it's own power (hole number *i* has the power *a*_{i}). If you throw a ball into hole *i* it will immediately jump to hole *i* + *a*_{i}, then it will jump out of it and so on. If there is no hole with such number, the ball will just jump out of the row. On each of the *M* moves the player can perform one of two actions:

- Set the power of the hole
*a*to value*b*. - Throw a ball into the hole
*a*and count the number of jumps of a ball before it jump out of the row and also write down the number of the hole from which it jumped out just before leaving the row.

Petya is not good at math, so, as you have already guessed, you are to perform all computations.

Input

The first line contains two integers *N* and *M* (1 ≤ *N* ≤ 10^{5}, 1 ≤ *M* ≤ 10^{5}) — the number of holes in a row and the number of moves. The second line contains *N* positive integers not exceeding *N* — initial values of holes power. The following *M* lines describe moves made by Petya. Each of these line can be one of the two types:

- 0
*a**b* - 1
*a*

Output

For each move of the type 1 output two space-separated numbers on a separate line — the number of the last hole the ball visited before leaving the row and the number of jumps it made.

Examples

Input

8 5

1 1 1 1 1 2 8 2

1 1

0 1 3

1 1

0 3 4

1 2

Output

8 7

8 5

7 3

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/04/2023 06:38:46 (k1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|