Informática Avançado - Semana 70

Buracos

A pequena Suysa de Louza gosta de brincar muito. Acima de tudo, ele gosta de jogar um jogo Buracos. Este é um jogo para uma pessoa com as seguintes regras:

Existem N orifícios localizados em uma única linha e numerados da esquerda para a direita com números de 1 a N. Cada orifício tem sua própria potência (número do orifício i tem a potência a_i). Se você atirar uma bola para o buraco i, ela imediatamente saltará para o buraco i + a_i. Se não houver um buraco com esse número, a bola simplesmente saltará da fila. Em cada um dos movimentos M, o jogador pode executar uma das duas ações:

  • Defina a potência do furo a para o valor b.
  • Jogue uma bola no buraco a e conte o número de saltos de uma bola antes de pular para fora da linha e também anote o número do buraco do qual pulou antes de sair da linha.

Suysa de Louza não é bom em matemática, então, como você já adivinhou, você deve executar todos os cálculos.

Entrada

A primeira linha contém dois números inteiros N e M (1 \leq N \leq 10^5, 1 \leq M \leq 10^5) - o número de furos em uma linha e o número de movimentos. A segunda linha contém N números inteiros positivos que não excedem N - valores iniciais da potência dos furos. As seguintes linhas M descrevem movimentos feitos por Petya. Cada uma dessas linhas pode ser um dos dois tipos:

  • 0 a b
  • 1 a

Tipo 0 significa que é necessário definir a potência do buraco a para b, e tipo 1 significa que é necessário jogar uma bola no a-ésimo buraco. Os números a e b são números inteiros positivos que não excedem N.

Saída

Para cada jogada do tipo 1, imprima dois números separados por espaço em uma linha separada - o número do último buraco que a bola visitou antes de sair da linha e o número de saltos que fez.

Exemplos

ENTRADA SAÍDA
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

Enviar solução: codeforces