E. Лунки
ограничение по времени на тест
1 second
ограничение по памяти на тест
64 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Маленький Петя очень любит играть. Больше всего он любит играть в игру «Лунки». Это игра для одного игрока со следующими правилами:

Есть N лунок, расположенных в ряд, пронумерованных слева направо числами от 1 до N. У каждой лунки изначально установлена своя сила выброса (у лунки с номером i она равна ai). Если вбросить шарик в лунку i, то он тут же вылетит из нее и попадет в лунку i + ai, после чего он опять вылетит и т.д.. Если же лунки с таким номером нету, то он просто вылетит за край ряда. На каждом из M ходов игрок выбирает одно из двух действий:

  • Установить силу выброса лунки a равной b.
  • Вбросить шарик в лунку a и посчитать количество прыжков шарика, прежде чем он вылетит за край ряда, а так же записать номер лунки, после выпрыгивания из которой шарик вылетел за край.

У Пети есть некоторые проблемы с математикой, поэтому, как Вы уже догадались, именно Вам предстоит произвести все подсчеты.

Входные данные

Первая строка содержит два числа N и M (1 ≤ N ≤ 105, 1 ≤ M ≤ 105) — количество лунок в ряду и количество ходов. Следующая строка содержит N целых положительных чисел, не превышающих N - изначальные силы выброса лунок. Следующие M строк задают ходы, сделанные Петей. Каждая строка может быть двух типов:

  • 0 a b
  • 1 a
Тут, первый тип означает что требуется установить силу выброса лунки a равной b, а второй означает что требуется вбросить мячик в лунку с номером a. Числа a и b - целые положительные и не превышают N.
Выходные данные

Для каждого хода второго типа (задающего вбрасывание шарика) в порядке следования во входном файле выведите два числа через пробел в отдельной строке — номер последней лунки перед вылетом шарика за край и количество прыжков.

Примеры
Входные данные
8 5
1 1 1 1 1 2 8 2
1 1
0 1 3
1 1
0 3 4
1 2
Выходные данные
8 7
8 5
7 3