In a computer organization laboratory course, the instructor has arranged $n$ experiments for students to choose from.

There are $m$ events that occur sequentially in time. Each event is one of the following two types:

• 1 i x: A student with ID $x$ chooses experiment $i$. If they are the $j$-th student to choose this experiment, their sequence number for this experiment is $j$.
• 2 i1 j1 i2 j2: The student with sequence number $j_1$ in experiment $i_1$ and the student with sequence number $j_2$ in experiment $i_2$ swap their experiments. More specifically, if the student with sequence number $j_1$ in experiment $i_1$ previously had ID $x_1$, and the student with sequence number $j_2$ in experiment $i_2$ previously had ID $x_2$, then after the swap, the student with sequence number $j_1$ in experiment $i_1$ has ID $x_2$, and the student with sequence number $j_2$ in experiment $i_2$ has ID $x_1$.

After these $m$ events occur, the instructor needs to print the course roster. Finally, for each experiment, output the number of students, followed by the IDs of the students in increasing order of their sequence numbers.

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 each describe an event in one of the following two formats, given in chronological order:

• 1 i x: A student with ID $x$ chooses experiment $i$. It is guaranteed that all given values are integers, $1 \le i \le n$, $10^8 \le x < 10^9$, and that this student with ID $x$ has not chosen any experiment previously.
• 2 i1 j1 i2 j2: The student with sequence number $j_1$ in experiment $i_1$ and the student with sequence number $j_2$ in experiment $i_2$ swap their experiments. It is guaranteed that all given values are integers, $1 \le i_1, i_2 \le n$, $i_1 \neq i_2$, that a student with sequence number $j_1$ exists in experiment $i_1$, and that a student with sequence number $j_2$ exists in experiment $i_2$.

Output

Output $n$ lines. For the $i$-th line, first output the number of students who chose experiment $i$. If the number is non-zero, output the IDs of the students who chose experiment $i$ in increasing order of their sequence numbers. Separate two adjacent integers on a line with a single space.

Examples

Input 1

3 4
1 1 250000001
1 3 250000006
2 3 1 1 1
1 1 250000003

Output 1

2 250000006 250000003
0
1 250000001

Input 2

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 2

0
1 501201700
4 314360098 927149742 271374639
678882127
2 835745037 468012503

Note

For the first example, the following tables represent the course roster after each event:

• 1 1 250000001:

• 1 3 250000006:

• 2 1 1 3 1:

• 1 1 250000003: