Маленький Петя очень любит играть. Больше всего он любит играть в игру «Лунки». Это игра для одного игрока со следующими правилами:
Есть N лунок, расположенных в ряд, пронумерованных слева направо числами от 1 до N. У каждой лунки изначально установлена своя сила выброса (у лунки с номером i она равна ai). Если вбросить шарик в лунку i, то он тут же вылетит из нее и попадет в лунку i + ai, после чего он опять вылетит и т.д.. Если же лунки с таким номером нету, то он просто вылетит за край ряда. На каждом из M ходов игрок выбирает одно из двух действий:
- Установить силу выброса лунки a равной b.
- Вбросить шарик в лунку a и посчитать количество прыжков шарика, прежде чем он вылетит за край ряда, а так же записать номер лунки, после выпрыгивания из которой шарик вылетел за край.
У Пети есть некоторые проблемы с математикой, поэтому, как Вы уже догадались, именно Вам предстоит произвести все подсчеты.
Выходные данные
Для каждого хода второго типа (задающего вбрасывание шарика) в порядке следования во входном файле выведите два числа через пробел в отдельной строке — номер последней лунки перед вылетом шарика за край и количество прыжков.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|