There are several people lining up. Initially, the queue is empty. At each time $t (t=1, 2, \dots, n)$, one of the following events occurs:

1. $x$: A new person joins the queue. Their ID is assigned sequentially. They stand behind the person with ID $x$ ($x=0$ means they stand at the front of the queue).
2. $i, y$: Let $t'$ be the time when the person with ID $i$ joined the queue. The operation at time $t'$ is modified to $1\ y$.
   • This modification affects all operations occurring after time $t'$.
3. $z$: Query the current position of the person with ID $z$ in the queue.

Input

The first line contains two integers $sub$ and $n$, representing the subtask ID and the number of operations, respectively.

Then $n$ lines follow. Each line starts with an integer $opt$ representing the operation type.

If $opt=1$, input one integer $x$.

If $opt=2$, input two integers $i, y$.

If $opt=3$, input one integer $z$.

It is guaranteed that for all operations, including modified operations, the people involved are already in the queue when the operation occurs.

Output

For each operation of type $3$, output one integer per line representing the position.

Examples

Input

0 8
1 0
1 1
1 2
3 2
2 2 0
3 1
3 2
3 3

Output

2
3
1
2

Note

Explanation of the example:

After the third operation, the queue is $1, 2, 3$.

After the fifth operation, the queue is $2, 3, 1$.

Subtasks

For all test cases, it is guaranteed that $1 \leq n \leq 300000$ and that $x, i, y, z$ are valid.

Subtask 0, 4 pts: $n \leq 500$.

Subtask 1, 19 pts: $opt \neq 2$.

Subtask 2, 21 pts: The number of operations of type $3$ does not exceed $200$.

Subtask 3, 23 pts: $opt, x, i, y, z$ are generated uniformly at random within valid ranges.

Subtask 4, 33 pts: No special restrictions.