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