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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
from collections import defaultdict, deque
sys.stdin.readline().split()
A = defaultdict(deque)
ans = []
for query in sys.stdin:
	if query[0] == '0':
		(t, x) = query[2:].split()
		A[t].append(x)
	elif query[0] == '1':
		ans.append(' '.join(A[query[2:-1]]) + '\n')
	else:
		(s, t) = query[2:].split()
		if A[t]:
			if len(A[s]) == 1:
				A[t].append(A[s][0])
			elif len(A[t]) == 1:
				A[s].appendleft(A[t][0])
				A[t] = A[s]
			else:
				A[t].extend(A[s])
		else:
			A[t] = A[s]
		A[s] = deque()
sys.stdout.writelines(ans)


from collections import deque
readline = open(0).readline
writelines = open(1, 'w').writelines
(N, Q) = map(int, readline().split())
ans = []
A = [deque() for i in range(N)]

def push(t, x):
	A[t].append(str(x))

def dump(t):
	ans.append(' '.join(A[t]))
	ans.append('\n')

def splice(s, t):
	if A[s]:
		if A[t]:
			if len(A[s]) == 1:
				A[t].append(A[s][0])
			elif len(A[t]) == 1:
				A[s].appendleft(A[t][0])
				A[t] = A[s]
			else:
				A[t].extend(A[s])
		else:
			A[t] = A[s]
		A[s] = deque()
C = [push, dump, splice].__getitem__
for i in range(Q):
	(t, *a) = map(int, readline().split())
	C(t)(*a)
writelines(ans)


def solve():
	from collections import deque
	from sys import stdin
	f_i = stdin
	(n, q) = map(int, f_i.readline().split())
	L = [deque() for i in range(n)]
	ans = []
	for op in (line.split() for line in f_i):
		op_type = op[0]
		if op_type == '0':
			L[int(op[1])].append(op[2])
		elif op_type == '1':
			ans.append(' '.join(L[int(op[1])]))
		else:
			s = int(op[1])
			ls = L[s]
			t = int(op[2])
			lt = L[t]
			if lt:
				if len(ls) == 1:
					lt.append(ls[0])
				elif len(lt) == 1:
					ls.appendleft(lt[0])
					L[t] = ls
				elif ls:
					lt.extend(ls)
			else:
				L[t] = ls
			L[s] = deque()
	print('\n'.join(ans))
solve()


from collections import deque
(n, q) = [int(x) for x in input().split()]
L = [deque() for _ in range(n)]
for _ in range(q):
	(c, t, x) = [int(x) for x in (input() + ' 0').split()][:3]
	if c == 0:
		L[t].append(x)
	elif c == 1:
		print(' '.join(map(str, L[t])))
	else:
		(s, t) = (t, x)
		if L[s]:
			if L[t]:
				if len(L[s]) == 1:
					L[t].append(L[s][0])
				elif len(L[t]) == 1:
					L[s].appendleft(L[t][0])
					L[t] = L[s]
				else:
					L[t].extend(L[s])
			else:
				L[t] = L[s]
			L[s] = deque()


from collections import deque
(n, q) = map(int, input().split())
L = [deque() for _ in range(n)]
for _ in range(q):
	(command, *list_num) = input().split()
	if command == '0':
		t = int(list_num[0])
		x = int(list_num[1])
		L[t].append(x)
	elif command == '1':
		t = int(list_num[0])
		print(*L[t])
	elif command == '2':
		s = int(list_num[0])
		t = int(list_num[1])
		if not L[s]:
			continue
		if L[t]:
			if len(L[s]) == 1:
				L[t].append(L[s][0])
			elif len(L[t]) == 1:
				L[s].appendleft(L[t][0])
				L[t] = L[s]
			else:
				L[t].extend(L[s])
		else:
			L[t] = L[s]
		L[s] = deque()
	else:
		raise


class Node:

	def __init__(self, val=None, prev=None, next=None):
		self.val = val
		self.prev = prev
		self.next = next

class DoublyLinkedList:

	def __init__(self):
		self.start = Node(val='START', prev=None, next=None)
		self.end = Node(val='END', prev=self.start, next=None)
		self.start.next = self.end

	def insert(self, x):
		new_node = Node(val=x, prev=self.end.prev, next=self.end)
		self.end.prev.next = new_node
		self.end.prev = new_node

	def dump(self):
		node_list = []
		crnode = self.start.next
		while crnode != self.end:
			node_list.append(crnode.val)
			crnode = crnode.next
		print(' '.join(list(map(str, node_list))))

	def extend(self, dll):
		self.end.prev.next = dll.start.next
		dll.start.next.prev = self.end.prev
		self.end = dll.end
(n, q) = list(map(int, input().split(' ')))
splice = [DoublyLinkedList() for i in range(n)]
for i in range(q):
	(op, *val) = list(map(int, input().split(' ')))
	if op == 0:
		splice[val[0]].insert(val[1])
	elif op == 1:
		splice[val[0]].dump()
	else:
		splice[val[1]].extend(splice[val[0]])
		splice[val[0]] = DoublyLinkedList()


from collections import deque
import sys
(n, q) = map(int, input().split())
Q = [deque() for _ in range(n)]
ans = []
for query in (line.split() for line in sys.stdin):
	s = int(query[1])
	if query[0] == '0':
		t = int(query[2])
		Q[s].append(t)
	elif query[0] == '1':
		print(*Q[s])
	elif query[0] == '2':
		t = int(query[2])
		if Q[t]:
			if len(Q[s]) == 1:
				Q[t].append(Q[s][0])
			elif len(Q[t]) == 1:
				Q[s].appendleft(Q[t][0])
				Q[t] = Q[s]
			else:
				Q[t].extend(Q[s])
		else:
			Q[t] = Q[s]
		Q[s] = deque()


from collections import deque
(que_num, query_num) = map(lambda x: int(x), input().split())
ques = [deque() for _ in range(que_num)]
for _ in range(query_num):
	(op, *value) = map(lambda x: int(x), input().split())
	if 0 == op:
		ques[value[0]].append(value[1])
	elif 1 == op:
		if ques[value[0]]:
			print(' '.join([str(elem) for elem in ques[value[0]]]))
		else:
			print('')
	elif 2 == op:
		if ques[value[1]]:
			if len(ques[value[0]]) == 1:
				ques[value[1]].append(ques[value[0]][0])
			elif len(ques[value[1]]) == 1:
				ques[value[0]].appendleft(ques[value[1]][0])
				ques[value[1]] = ques[value[0]]
			else:
				ques[value[1]] += ques[value[0]]
		else:
			ques[value[1]] = ques[value[0]]
		ques[value[0]] = deque()
	else:
		pass


from collections import deque

def main():
	(n, q) = map(int, input().split())
	li = [deque() for i in range(n)]
	for _ in range(q):
		(command, *para) = map(int, input().split())
		if command == 0:
			li[para[0]].append(para[1])
		elif command == 1:
			print(*li[para[0]])
		elif command == 2:
			if not li[para[0]]:
				continue
			if not li[para[1]]:
				li[para[1]] = li[para[0]]
			elif len(li[para[0]]) == 1:
				li[para[1]].append(li[para[0]][0])
			elif len(li[para[1]]) == 1:
				li[para[0]].appendleft(li[para[1]][0])
				li[para[1]] = li[para[0]]
			else:
				li[para[1]].extend(li[para[0]])
			li[para[0]] = deque()
main()


class Node:

	def __init__(self, key):
		self.key = key
		self.next = None

class List:

	def __init__(self):
		self.head = Node(0)
		self.tail = self.head

	def insert(self, key):
		self.tail.next = Node(key)
		self.tail = self.tail.next

	def dump(self):
		p = self.head.next
		while p != None:
			print(p.key, end='')
			if p.next != None:
				print(' ', end='')
			p = p.next
		print()

	def splice(self, other):
		other.tail.next = self.head.next
		other.tail = self.tail
		self.head.next = None
		self.tail = self.head
(n, q) = map(int, input().split())
SList = [List() for i in range(n)]
for i in range(q):
	(com, index, *n) = map(int, input().split())
	if com == 0:
		SList[index].insert(n[0])
	elif com == 1:
		SList[index].dump()
	elif com == 2:
		SList[index].splice(SList[n[0]])


def resolve():
	import sys
	from collections import deque

	def input():
		return sys.stdin.readline().rstrip()
	(n, Q) = [int(i) for i in input().split()]
	A = [deque() for _ in range(n)]
	for _ in range(Q):
		q = [int(i) for i in input().split()]
		if q[0] == 0:
			A[q[1]].append(q[2])
		elif q[0] == 1:
			print(*A[q[1]])
		else:
			if len(A[q[2]]) == 0:
				A[q[2]] = A[q[1]]
			elif len(A[q[2]]) == 1:
				A[q[1]].appendleft(A[q[2]][0])
				A[q[2]] = A[q[1]]
			else:
				A[q[2]].extend(A[q[1]])
			A[q[1]] = deque()
resolve()


class Node:

	def __init__(self, value=0):
		self.key = value
		(self.prev, self.next) = (None, None)

class Lst:

	def __init__(self):
		self.nil = Node('END')
		self.nil.next = self.nil
		self.nil.prev = self.nil
		self.cur = self.nil

	def insert(self, value):
		x = Node(value)
		x.prev = self.cur
		x.prev.next = x
		x.next = self.nil
		self.cur = x

	def dump(self):
		res = []
		cur = self.nil
		while cur.next.key != 'END':
			cur = cur.next
			res.append(cur.key)
		print(*res)

class Sp:

	def __init__(self, n):
		self.lst = [Lst() for _ in range(n)]

	def insert(self, t, x):
		self.lst[t].insert(x)

	def dump(self, t):
		self.lst[t].dump()

	def splice(self, s, t):
		self.lst[t].cur.next = self.lst[s].nil.next
		self.lst[s].nil.next.prev = self.lst[t].cur
		self.lst[t].cur = self.lst[s].cur
		self.lst[s] = Lst()
(n, q) = map(int, input().split())
lst = Sp(n)
for _ in range(int(q)):
	(op, t, x) = (input() + ' 1').split()[:3]
	if op == '0':
		lst.insert(int(t), int(x))
	elif op == '1':
		lst.dump(int(t))
	else:
		lst.splice(int(t), int(x))


from collections import deque
(n, q) = map(int, input().split())
L = {i: deque() for i in range(n)}
for _ in range(q):
	(*qi,) = map(int, input().split())
	if qi[0] == 0:
		(t, x) = (qi[1], qi[2])
		L[t].append(x)
	elif qi[0] == 1:
		print(*L[qi[1]])
	else:
		(s, t) = (qi[1], qi[2])
		if len(L[s]) < len(L[t]):
			L[t].extend(L[s])
			L[s] = deque()
		else:
			while L[t]:
				L[s].appendleft(L[t].pop())
			L[t] = L[s]
			L[s] = deque()


from collections import deque
(n, queries) = map(int, input().split())
L = [deque() for _ in range(n)]
for _ in range(queries):
	(q, *list_num) = input().split()
	if q == '0':
		t = int(list_num[0])
		x = int(list_num[1])
		L[t].append(x)
	elif q == '1':
		t = int(list_num[0])
		print(*L[t])
	elif q == '2':
		s = int(list_num[0])
		t = int(list_num[1])
		if not L[s]:
			continue
		if L[t]:
			if len(L[s]) == 1:
				L[t].append(L[s][0])
			elif len(L[t]) == 1:
				L[s].appendleft(L[t][0])
				L[t] = L[s]
			else:
				L[t].extend(L[s])
		else:
			L[t] = L[s]
		L[s] = deque()


from sys import stdin, stdout
from collections import defaultdict, deque
(n, q) = map(int, stdin.readline().split())
queries = stdin.readlines()
A = defaultdict(deque)
ans = []
for query in queries:
	query = query.split()
	if query[0] == '0':
		A[int(query[1])].append(query[2])
	elif query[0] == '1':
		ans.append(' '.join(A[int(query[1])]) + '\n')
	else:
		s = int(query[1])
		t = int(query[2])
		if A[t]:
			if len(A[s]) == 1:
				A[t].append(A[s][0])
			elif len(A[t]) == 1:
				A[s].appendleft(A[t][0])
				A[t] = A[s]
			else:
				A[t].extend(A[s])
		else:
			A[t] = A[s]
		A[s] = deque()
stdout.writelines(ans)


class Node:

	def __init__(self, value):
		self.value = value
		self.next = None

class List:

	def __init__(self):
		self.head = None
		self.tail = None

	def insert(self, v):
		node = Node(v)
		if self.tail is None:
			self.head = node
			self.tail = node
		else:
			self.tail.next = node
			self.tail = node

	def dump(self):
		node = self.head
		while node is not None:
			yield node.value
			node = node.next

	def splice(self, li):
		if self.head is None:
			self.head = li.head
			self.tail = li.tail
		else:
			self.tail.next = li.head
			self.tail = li.tail
		li.clear()

	def clear(self):
		self.head = None
		self.tail = None

def run():
	(n, q) = [int(x) for x in input().split()]
	ls = [List() for _ in range(n)]
	for _ in range(q):
		com = [int(x) for x in input().split()]
		c = com[0]
		if c == 0:
			(t, v) = com[1:]
			ls[t].insert(v)
		elif c == 1:
			t = com[1]
			values = []
			for v in ls[t].dump():
				values.append(str(v))
			print(' '.join(values))
		elif c == 2:
			(s, t) = com[1:]
			ls[t].splice(ls[s])
		else:
			raise ValueError('invalid command')
run()


import sys
from collections import deque, defaultdict
A = defaultdict(deque)
sys.stdin.readline().split()
ans = []
for query in sys.stdin:
	if query[0] == '0':
		(t, x) = query[2:].split()
		A[t].append(x)
	elif query[0] == '1':
		ans.append(' '.join(A[query[2:-1]]) + '\n')
	else:
		(s, t) = query[2:].split()
		if A[t]:
			if len(A[s]) == 1:
				A[t].append(A[s][0])
			elif len(A[t]) == 1:
				A[s].appendleft(A[t][0])
				A[t] = A[s]
			else:
				A[t].extend(A[s])
		else:
			A[t] = A[s]
		A[s] = deque()
sys.stdout.writelines(ans)


from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)

def input():
	return sys.stdin.readline().strip()
(n, q) = map(int, input().split())
L = deque((deque() for i in range(n)))
for i in range(q):
	query = input().split()
	if query[0] == '0':
		L[int(query[1])].append(query[2])
	elif query[0] == '1':
		print(' '.join(L[int(query[1])]))
	else:
		s = int(query[1])
		t = int(query[2])
		if len(L[s]):
			if len(L[t]) == 0:
				L[t] = L[s]
			elif len(L[t]) == 1:
				L[s].appendleft(L[t][0])
				L[t] = L[s]
			else:
				L[t].extend(L[s])
		elif len(L[s]) == 1:
			L[t].append(L[t][0])
		L[s] = deque()


from collections import deque
(n, q) = list(map(int, input().split()))
L = [deque() for _ in range(n)]
for i in range(q):
	query = input()
	if query[0] == '0':
		(_, t, x) = list(map(int, query.split()))
		L[t].append(x)
	elif query[0] == '1':
		(_, t) = list(map(int, query.split()))
		print(*L[t])
	else:
		(_, s, t) = list(map(int, query.split()))
		if L[t]:
			if len(L[s]) == 1:
				L[t].append(L[s][0])
			elif len(L[t]) == 1:
				L[s].appendleft(L[t][0])
				L[t] = L[s]
			else:
				L[t].extend(L[s])
		else:
			L[t] = L[s]
		L[s] = deque()


import collections

class Splice:

	def __init__(self, num_lists):
		self.lists = [collections.deque() for i in range(0, num_lists, 1)]

	def insert(self, t, x):
		self.lists[t].append(x)
		return self

	def dump(self, t):
		print(' '.join(map(str, self.lists[t])))

	def splice(self, s, t):
		if self.lists[t]:
			if len(self.lists[s]) == 1:
				self.lists[t].append(self.lists[s][0])
			elif len(self.lists[t]) == 1:
				self.lists[s].appendleft(self.lists[t][0])
				self.lists[t] = self.lists[s]
			else:
				self.lists[t].extend(self.lists[s])
		else:
			self.lists[t] = self.lists[s]
		self.lists[s] = collections.deque()
		return self
(num_lists, num_op) = map(int, input().split(' '))
lists = Splice(num_lists)
for op in range(0, num_op):
	op = tuple(map(int, input().split(' ')))
	if op[0] == 0:
		lists.insert(op[1], op[2])
	elif op[0] == 1:
		lists.dump(op[1])
	elif op[0] == 2:
		lists.splice(op[1], op[2])


from collections import deque
(n, q) = map(int, input().split())
lists = [deque() for i in range(n)]
while q:
	q -= 1
	s = [*map(int, input().split())]
	if s[0] == 0:
		lists[s[1]].append(s[2])
	elif s[0] == 1:
		print(*lists[s[1]])
	else:
		(l1, l2) = (lists[s[1]], lists[s[2]])
		if len(l1) < len(l2):
			l2.extend(l1)
			l1.clear()
		else:
			while len(l2):
				l1.appendleft(l2[-1])
				l2.pop()
			(lists[s[1]], lists[s[2]]) = (lists[s[2]], lists[s[1]])


import sys
input = sys.stdin.readline
from collections import deque
(N, Q) = map(int, input().split())
L = [deque([]) for _ in range(N)]
for _ in range(Q):
	q = list(map(int, input().split()))
	if q[0] == 0:
		L[q[1]].append(q[2])
	elif q[0] == 1:
		if L[q[1]]:
			print(' '.join(map(str, L[q[1]])))
		else:
			print()
	else:
		if L[q[1]]:
			if L[q[2]]:
				if len(L[q[1]]) == 1:
					L[q[2]].append(L[q[1]][0])
				elif len(L[q[2]]) == 1:
					L[q[1]].appendleft(L[q[2]][0])
					L[q[2]] = L[q[1]]
				else:
					L[q[2]].extend(L[q[1]])
			else:
				L[q[2]] = L[q[1]]
		L[q[1]] = deque([])


import sys
from collections import deque
sys.setrecursionlimit(10 ** 9)
(n, q) = map(int, input().split())
l = [deque() for _ in range(n)]
for _ in range(q):
	query = input().split()
	if query[0] == '0':
		idx = int(query[1])
		l[idx].append(query[2])
	elif query[0] == '1':
		idx = int(query[1])
		print(' '.join(l[idx]))
	elif query[0] == '2':
		idx1 = int(query[1])
		idx2 = int(query[2])
		if len(l[idx1]) > 1:
			if len(l[idx2]) == 0:
				l[idx2] = l[idx1]
			elif len(l[idx2]) == 1:
				l[idx1].appendleft(l[idx2][0])
				l[idx2] = l[idx1]
			else:
				l[idx2].extend(l[idx1])
		elif len(l[idx1]) == 1:
			l[idx2].append(l[idx1][0])
		l[idx1] = deque()


from collections import deque

def insert(t, x):
	Llist[t].append(x)

def dump(t):
	print(*Llist[t])

def splice(s, t):
	if Llist[t]:
		if len(Llist[t]) == 1:
			Llist[s].appendleft(Llist[t][0])
			Llist[t] = Llist[s]
		elif len(Llist[s]) == 1:
			Llist[t].append(Llist[s][0])
		else:
			Llist[t].extend(Llist[s])
	else:
		Llist[t] = Llist[s]
	Llist[s] = deque()
(n, q) = map(int, input().split())
Llist = []
for i in range(n):
	Llist.append(deque())
for i in range(q):
	queryi = list(map(int, input().split()))
	if queryi[0] == 0:
		insert(queryi[1], queryi[2])
	elif queryi[0] == 1:
		dump(queryi[1])
	else:
		splice(queryi[1], queryi[2])


import sys

class Node:

	def __init__(self, next_node, prev_node, val):
		self.next = next_node
		self.prev = prev_node
		self.val = val

	def __repr__(self):
		return f'{self.val}'

class DoubleLinkedList:

	def __init__(self):
		self.head = Node(None, None, None)
		self.tail = self.head

	def append(self, val):
		node = Node(None, self.tail, val)
		self.tail.next = node
		self.tail = node

	def dump(self):
		cur = self.head.next
		out = ''
		while cur is not None:
			out += f'{cur.val} '
			cur = cur.next
		print(out[:-1])

	def splice(self, other):
		self.tail.next = other.head.next
		self.tail = other.tail

	def clear(self):
		self.__init__()
(n, q) = map(int, input().split())
lists = {str(i): DoubleLinkedList() for i in range(n)}
lines = sys.stdin.readlines()
for i in range(q):
	(query, *arg) = lines[i].split()
	if query == '0':
		lists[arg[0]].append(arg[1])
	elif query == '1':
		lists[arg[0]].dump()
	elif query == '2':
		lists[arg[1]].splice(lists[arg[0]])
		lists[arg[0]].clear()
	else:
		raise AssertionError


import heapq
import collections
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
L = [collections.deque() for i in range(n)]
queries = list()
for i in range(q):
	queries.append(list(map(int, input().split())))
for query in queries:
	if query[0] == 0:
		L[query[1]].append(query[2])
	elif query[0] == 1:
		print(*L[query[1]])
	elif query[0] == 2:
		if L[query[2]]:
			if len(L[query[1]]) == 1:
				L[query[2]].append(L[query[1]][0])
			elif len(L[query[2]]) == 1:
				L[query[1]].appendleft(L[query[2]][0])
				L[query[2]] = L[query[1]]
			else:
				L[query[2]].extend(L[query[1]])
		else:
			L[query[2]] = L[query[1]]
		L[query[1]] = collections.deque()