J. Just reseat!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Principle of Computer Organization lab course, the instructor has arranged $$$n$$$ experiments for students to choose from.

Subsequently, $$$m$$$ events occur in chronological order. Each event takes one of the following two forms:

  • $$$1\ i\ x$$$: A student with student ID $$$x$$$ chooses experiment $$$i$$$. If this student is the $$$j$$$-th student to choose this experiment, then their index in this experiment is $$$j$$$.
  • $$$2\ i_1\ j_1\ i_2\ j_2$$$: The student with index $$$j_1$$$ in experiment $$$i_1$$$ and the student with index $$$j_2$$$ in experiment $$$i_2$$$ swap experiments. More precisely, if before the swap, the student with index $$$j_1$$$ in experiment $$$i_1$$$ has student ID $$$x_1$$$, and the student with index $$$j_2$$$ in experiment $$$i_2$$$ has student ID $$$x_2$$$, then after the swap, the student with index $$$j_1$$$ in experiment $$$i_1$$$ will have student ID $$$x_2$$$, and the student with index $$$j_2$$$ in experiment $$$i_2$$$ will have student ID $$$x_1$$$.

After all $$$m$$$ events have occurred, the instructor needs to print the course roster. Finally, for each experiment, you need to output the number of students, followed by the IDs of the students in this experiment, in ascending order of index.

Input

The first line contains two integers $$$n, m$$$ ($$$1 \le n, m \le 3 \times 10^5$$$), representing the number of experiments and the number of events, respectively.

The next $$$m$$$ lines describe each event in chronological order, following one of the two formats below:

  • $$$1\ i\ x$$$: Student with ID $$$x$$$ selects the $$$i$$$th experiment. It is guaranteed that all values are integers, $$$1\le i\le n,10^{8}\le x \lt 10^{9}$$$, and this student has not selected any experiment before.

  • $$$2\ i_1 \ j_1 \ i_2\ j_2$$$: Student $$$j_1$$$ (assigned to experiment $$$i_1$$$) swapped experiments with student $$$j_2$$$ (assigned to experiment $$$i_2$$$). It is guaranteed that all given values are integers, $$$1\le i_1,i_2\le n$$$ and $$$i_1\not= i_2$$$. Student $$$j_1$$$ is assigned to experiment $$$i_1$$$, and student $$$j_2$$$ is assigned to experiment $$$i_2$$$.
Output

Output $$$n$$$ lines.

For the $$$i$$$-th line, first output the number of students who have chosen experiment $$$i$$$. If this number is non-zero, then output the student IDs of the students in experiment $$$i$$$ in ascending order of index. Adjacent integers on the same line should be separated by a single space.

Examples
Input
3 4
1 1 250000001
1 3 250000006
2 3 1 1 1
1 1 250000003
Output
2 250000006 250000003
0
1 250000001
Input
4 9
1 3 835745037
1 3 927149742
1 2 468012503
1 4 314360098
2 3 1 4 1
1 4 501201700
1 3 271374639
2 4 2 2 1
1 3 678882127
Output
0
1 501201700
4 314360098 927149742 271374639 678882127
2 835745037 468012503