Problem B
Collection

Marco é um famoso colecionador de discos de vinil. Como todo colecionador sério, Marco identifica cada disco em sua coleção com um número.

Marco separa seus discos em playlists, para que possa apreciá-los da melhor maneira possível. E como todo colecionador excêntrico, ele é cheio de manias na hora de organizar seus discos. Marco modifica suas playlists juntando duas em uma só, ou removendo alguns discos do fim de uma para criar outra.

Cada playlist de Marco é identificada com um número. Quando duas playlists são unidas, Marco guarda o número da segunda em uma pilha de números. Assim que uma playlist é criada, Marco pega o número no topo da pilha e o usa para identificar a nova playlist.

Como a coleção está muito grande, Marco te contratou para organizar os vinis. Como se não bastasse manter tudo em ordem, Marco também cobra que você conheça a coleção. Por isso te pergunta frequentemente qual disco está em qual lugar.

Marco te dará tres tipos de ordens, cada uma pode ser identificada por dois números $i$ e $j$:

• Tipo $1$: Você deve dizer qual o $j$-ésimo disco da playlist $i$.

• Tipo $2$: Você deve adicionar os discos da playlist $j$ à playlist $i$.

• Tipo $3$: Você deve manter os $j$ primeiros elementos da playlist $i$ e criar uma nova playlist com o restante dos discos.

Marco é muito atento, então toda ordem que ele dá é válida, ou seja, ele não mencionará playlists inexistentes e não criará playlists vazias. Se Marco te pergunta qual disco está em certa posição de qualquer playlist e tal disco não existir é porque voce errou alguma ordem anterior.

Para facilitar sua chegada ao novo trabalho, Marco criou playlist de $1$ a $n$, cada uma com apenas um disco de vinil.

Input

A primeira linha contém dois inteiros $n$ e $q$ ($1 < n \le 10^5$, $1 < q \le 10^6$), o número de discos e o número de ordens que Marco lhe dará. Seguem-se $q$ linhas, onde a $i$-ésima linha contém $t$ – o tipo da ordem de Marco – e $i$, $j$ que descrevem a ordem dada.

Output

Para cada ordem do tipo $1$, você deve imprimir uma linha com o número do disco que satisfaz a ordem de Marco.

2 2
1 1 1
1 2 1

1
2

3 3
2 1 2
2 1 3
1 1 3

3

2 3
2 1 2
3 1 1
1 2 1

2