Problem: For $n$ lists $L_i$ $(i = 0, 1, ..., n-1)$, perform a sequence of the following operations.

* insert($t$, $x$): Insert an integer $x$ at the end of $L_t$.
* dump($t$): Print all elements in $L_t$.
* splice($s$, $t$): Transfer elements of $L_s$ to the end of $L_t$. $L_s$ becomes empty.



In the initial state, $L_i$ $(i = 0, 1, ..., n-1)$ are empty.

Constraints

* $1 \leq n \leq 1,000$
* $1 \leq q \leq 500,000$
* For a splice operation, $s \ne t$
* For a splice operation, $L_s$ is not empty
* The total number of elements printed by dump operations do not exceed 1,000,000
* $-1,000,000,000 \leq x \leq 1,000,000,000$

Input

The input is given in the following format.


$n \; q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $t$ $x$


or


1 $t$


or


2 $s$ $t$


where the first digits 0, 1 and 2 represent insert, dump and splice operations respectively.

Output

For each dump operation, print elements of the corresponding list in a line. Separete adjacency elements by a space character (do not print the space after the last element). Note that, if the list is empty, an empty line should be printed.

Example

Input

3 10
0 0 1
0 0 2
0 0 3
0 1 4
0 1 5
2 1 0
0 2 6
1 0
1 1
1 2


Output

1 2 3 4 5

6

Solution (in JAVA):

Solution:
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			int listNum = sc.nextInt();
			int qLen = sc.nextInt();
			MyList[] lists = new MyList[listNum];

			for(int i=0;i<listNum;i++) {
				lists[i] = new MyList();
			}

			for(int i=0;i<qLen;i++) {
				int query = sc.nextInt();
				int t = sc.nextInt();
				switch(query) {
				case 0:
					lists[t].insert(sc.nextInt());;
					break;
				case 1:
					lists[t].dump();
					break;
				case 2:
					lists[sc.nextInt()].splice(lists[t]);
					break;
				}
			}
		}
	}
	/**
	 * リストの各要素です
	 */
	static class MyNode{
		int value;
		MyNode next;

		public MyNode(int value) {
			this.value = value;
			this.next = null;
		}
		/**
		 * 次要素をセットします
		 * @param node 次要素
		 */
		public void setNext(MyNode node) {
			this.next = node;
		}
	}
	/**
	 * 自作(単方向)リスト
	 */
	static class MyList{
		MyNode head;
		MyNode last;
		public MyList() {
			this.head = null;
			this.last = null;
		}
		/**
		 * リストに要素を追加します
		 * @param x
		 */
		public void insert(int x) {
			MyNode node = new MyNode(x);
			if(this.head == null) {
				this.head = node;
				this.last = node;
			}
			else {
				this.last.setNext(node);
				this.last = node;
			}
		}
		/**
		 * これに引数のリストを連結し、引数リストは亡き者になります
		 * @param list
		 */
		public void splice(MyList list) {
			if(this.head == null) {
				this.head = list.head;
				this.last = list.last;
			}
			else {
				this.last.setNext(list.head);
				this.last = list.last;
			}
			list.head = null;
			list.last = null;
		}
		/**
		 * リストの全要素を表示します
		 */
		public void dump() {
			MyNode node = this.head;
			if(node != null) {
				System.out.print(node.value);
				for(node = node.next;node != null;node = node.next) {
					System.out.print(" " + node.value);
				}
			}
			System.out.println();
		}
	}
}