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

Enviar solução: codeforces