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