Buracos
A pequena Suysa de Louza gosta de brincar muito. Acima de tudo, ele gosta de jogar um jogo . Este é um jogo para uma pessoa com as seguintes regras:
Existem orifícios localizados em uma única linha e numerados da esquerda para a direita com números de a . Cada orifício tem sua própria potência (número do orifício tem a potência ). Se você atirar uma bola para o buraco , ela imediatamente saltará para o buraco . Se não houver um buraco com esse número, a bola simplesmente saltará da fila. Em cada um dos movimentos , o jogador pode executar uma das duas ações:
- Defina a potência do furo para o valor .
- Jogue uma bola no buraco 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 e - o número de furos em uma linha e o número de movimentos. A segunda linha contém números inteiros positivos que não excedem - valores iniciais da potência dos furos. As seguintes linhas descrevem movimentos feitos por Petya. Cada uma dessas linhas pode ser um dos dois tipos:
Tipo significa que é necessário definir a potência do buraco para , e tipo significa que é necessário jogar uma bola no -ésimo buraco. Os números e são números inteiros positivos que não excedem .
Saída
Para cada jogada do tipo , 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