Desvendando as Formigas

Wilson é um grande admirador de formigas e quer estudar melhor uma espécie, buscando aprender mais sobre seus hábitos.

Para isso, ele observa uma trilha reta, dividida em posições identificadas por números inteiros. Cada posição pode ser ocupada por, no máximo, uma formiga. No início do estudo, não há formigas na trilha.

Ao longo do estudo, acontecem três tipos de eventos (numerados de $1$ a $3$), cada um associado a um número (denotado por $x$):

• 1 x: uma nova formiga entra na posição $x$. Se já existia uma formiga nesta posição, a formiga antiga sai da trilha, sendo substituída pela nova.
• 2 x: a posição de toda formiga na trilha é incrementada em $x$. Ou seja, se $x > 0$, as formigas se deslocam $x$ posições para a direita; mas se $x < 0$, elas se deslocam $x$ posições para a esquerda.
• 3 x: Wilson conta quantas formigas na trilha estão à esquerda da posição $x$ — ou seja, quantas posições $p$ tais que $p < x$ possuem uma formiga.

Replique o estudo realizado por Wilson, processando os eventos na ordem em que ocorreram e imprimindo a quantidade contada por ele em cada evento do tipo $3$.

Entrada

A primeira linha contém um inteiro $Q$ $(1 \leq Q \leq 5 \cdot 10^5)$: o número de eventos.

Cada uma das próximas $Q$ linhas contém dois inteiros $t$ e $v$, com $t \in \{1,2,3\}$ e $|v| < 2^{63}$. $t$ é o tipo do evento e $v$ é o valor do número $x$ associado a este evento, mas codificado.

Para obter o valor real de $x$, você deve tomar $x = v \oplus r$, onde:

• $r$ é o valor do último resultado imprimido para um evento do tipo $3$. Se nenhum evento do tipo $3$ tiver ocorrido até o evento atual, considere que $r = 0$ e, portanto, $x = v$.
• $\oplus$ é operação de XOR bit a bit entre a representação de números inteiros em $64$ bits.
• A representação de um número $a$ (tal que $|a| < 2^{63}$) em $64$ bits corresponde aos $64$ dígitos binários menos significativos do número $a$, se $a \geq 0$. Se $a < 0$, a representação corresponde aos mesmos dígitos, mas de $2^{64} + a$.

Isso significa que o valor de $x$ pode ser obtido pela representação binária resultante da operação $v \oplus r$. Nessa representação, se o $64$-ésimo bit menos significativo possuir valor $0$, os dígitos binários representam exatamente o número $x$. Caso contrário, eles representam $2^{64} + x$. É garantido que $|x| \leq 10^9$.

Além disso, também é garantido que existe pelo menos um evento do tipo $3$.

Saída

Para cada evento do tipo $3$, imprima uma linha contendo um único inteiro: a quantidade de formigas na trilha em posições à esquerda de $x$.

Observações

Note que, se sua solução imprimir um valor incorreto para um evento do tipo $3$, para os eventos seguintes o valor de $x$ pode ser decodificado incorretamente (considerando que a solução atualiza $r$ de acordo). Perceba que isso pode resultar em vereditos diferentes de Wrong Answer, mesmo que a solução de fato tenha imprimido um resultado incorreto.

12
1 3
1 -2
3 3
1 3
1 3
2 -3
3 -2
1 -4
2 7
3 6
3 -12
3 100

1
2
2
0
3