atcoder#ABC279F. [ABC279F] BOX

[ABC279F] BOX

Score : 500500 points

Problem Statement

There are NN boxes numbered 1,2,,N1,2,\ldots,N, and 1010010^{100} balls numbered 1,2,,101001,2,\dots,10^{100}. Initially, box ii contains just ball ii.

Process a total of QQ operations that will be performed.

There are three types of operations: 11, 22, and 33.

Type 11: Put all contents of box YY into box XX. It is guaranteed that XYX \neq Y.

1 X Y

Type 22: Put ball k+1k+1 into box XX, where kk is the current total number of balls contained in the boxes.

2 X

Type 33: Report the number of the box that contains ball XX.

3 X

Constraints

  • All values in the input are integers.
  • 2N3×1052 \le N \le 3 \times 10^5
  • 1Q3×1051 \le Q \le 3 \times 10^5
  • For each type-11 operation, 1X,YN1 \le X,Y \le N and XYX \neq Y.
  • For each type-22 operation, 1XN1 \le X \le N.
  • For each type-33 operation, ball XX is contained in some box at that point.
  • There is at least one type-33 operation.

Input

The input is given from Standard Input in the following format. Here, opiop_i represents the ii-th operation.

NN QQ

op1op_1

op2op_2

\vdots

opQop_Q

Output

For each type-33 operation, print a line containing the response as an integer.

5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6
5
4
3
1
3

This input contains ten operations.

  • The first operation is of type 33. Ball 55 is in box 55.
  • The second operation is of type 11. Put all contents of box 44 into box 11.- Box 11 now contains balls 11 and 44, and box 44 is now empty.
  • Box 11 now contains balls 11 and 44, and box 44 is now empty.
  • The third operation is of type 22. Put ball 66 into box 11.
  • The fourth operation is of type 22. Put ball 77 into box 44.
  • The fifth operation is of type 33. Ball 77 is in box 44.
  • The sixth operation is of type 11. Put all contents of box 11 into box 33.- Box 33 now contains balls 11, 33, 44, and 66, and box 11 is now empty.
  • Box 33 now contains balls 11, 33, 44, and 66, and box 11 is now empty.
  • The seventh operation is of type 33. Ball 44 is in box 33.
  • The eighth operation is of type 11. Put all contents of box 44 into box 11.- Box 11 now contains ball 77, and box 44 is now empty.
  • Box 11 now contains ball 77, and box 44 is now empty.
  • The ninth operation is of type 33. Ball 77 is in box 11.
  • The tenth operation is of type 33. Ball 66 is in box 33.