Write a program which reads a sequence of integers $A = \\{a_0, a_1, ..., a_{n-1}\\}$ and swap specified elements by a list of the following operation:

* swapRange($b, e, t$): For each integer $k$ ($0 \leq k < (e - b)$, swap element $(b + k)$ and element $(t + k)$.

Constraints

* $1 \leq n \leq 1,000$
* $-1,000,000,000 \leq a_i \leq 1,000,000,000$
* $1 \leq q \leq 1,000$
* $0 \leq b_i < e_i \leq n$
* $0 \leq t_i < t_i + (e_i - b_i) \leq n$
* Given swap ranges do not overlap each other

Input

The input is given in the following format.


$n$
$a_0 \; a_1 \; ...,\; a_{n-1}$
$q$
$b_1 \; e_1 \; t_1$
$b_2 \; e_2 \; t_2$
:
$b_{q} \; e_{q} \; t_{q}$


In the first line, $n$ (the number of elements in $A$) is given. In the second line, $a_i$ (each element in $A$) are given. In the third line, the number of queries $q$ is given and each query is given by three integers $b_i \; e_i \; t_i$ in the following $q$ lines.

Output

Print all elements of $A$ in a line after performing the given operations. Put a single space character between adjacency elements and a newline at the end of the last element.

Example

Input

11
1 2 3 4 5 6 7 8 9 10 11
1
1 4 7


Output

1 8 9 10 5 6 7 2 3 4 11

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
n = int(input())
num = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e, t) = map(int, input().split())
	for i in range(e - b):
		(num[b + i], num[t + i]) = (num[t + i], num[b + i])
print(' '.join((str(n) for n in num)))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, t) = map(int, input().split())
	if t > b:
		a = a[:b] + a[t:t + e - b] + a[e:t] + a[b:e] + a[t + e - b:]
	else:
		a = a[:t] + a[b:e] + a[t + e - b:b] + a[t:t + e - b] + a[e:]
print(*a)


def resolve():
	from collections import deque
	N = int(input())
	A = [int(i) for i in input().split()]
	Q = int(input())
	ans = [i for i in range(N)]
	for _ in range(Q):
		(b, e, t) = [int(i) for i in input().split()]
		tmp = deque(ans[t:t + (e - b)])
		for i in range(b, e):
			ans[i + t - b] = ans[i]
			ans[i] = tmp[i - b]
	prt = [0] * N
	for i in range(N):
		prt[i] = A[ans[i]]
	print(*prt)
resolve()


n = int(input())
box = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		(box[t + k], box[b + k]) = (box[b + k], box[t + k])
print(*box)


def my_swap(ary, b, e, t):
	k = 0
	while k < e - b:
		temp = ary[b + k]
		ary[b + k] = ary[t + k]
		ary[t + k] = temp
		k += 1
	return ary

def main():
	input()
	ary = [int(x) for x in input().split(' ')]
	q = int(input())
	for i in range(q):
		(b, e, t) = [int(x) for x in input().split(' ')]
		ary = my_swap(ary, b, e, t)
	print(' '.join([str(x) for x in ary]))
main()


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, t) = list(map(int, input().split()))
	for k in range(e - b):
		(a[b + k], a[t + k]) = (a[t + k], a[b + k])
print(' '.join(map(str, a)))


_ = input()
A = list(input().split())
for _ in range(int(input())):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		(A[b + k], A[t + k]) = (A[t + k], A[b + k])
print(*A, sep=' ')


input()
(*a,) = map(int, input().split())
for i in range(int(input())):
	(l, r, t) = map(int, input().split())
	(a[l:r], a[t:t + r - l]) = (a[t:t + r - l], a[l:r])
print(*a)


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, t) = list(map(int, input().split()))
	for j in range(e - b):
		(A[b + j], A[t + j]) = (A[t + j], A[b + j])
print(*A)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, t) = map(int, input().split())
	s = t + e - b
	if t > b:
		a = a[:b] + a[t:s] + a[e:t] + a[b:e] + a[s:]
	else:
		a = a[:t] + a[b:e] + a[s:b] + a[t:s] + a[e:]
print(*a)


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		(A[b + k], A[t + k]) = (A[t + k], A[b + k])
print(*A)


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	queryi = list(map(int, input().split()))
	b = queryi[0]
	e = queryi[1]
	t = queryi[2]
	for i in range(e - b):
		temp = A[b + i]
		A[b + i] = A[t + i]
		A[t + i] = temp
print(*A)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e, t) = map(int, input().split())
	x = a[t:t + e - b]
	a[t:t + e - b] = a[b:e]
	a[b:e] = x
print(' '.join(map(str, a)))


from sys import stdin
n = int(stdin.readline())
l = list(stdin.readline().split())
q = int(stdin.readline())
for i in range(q):
	inp_l = list(map(int, stdin.readline().split()))
	displacement = inp_l[1] - inp_l[0]
	for i in range(displacement):
		(l[inp_l[0] + i], l[inp_l[2] + i]) = (l[inp_l[2] + i], l[inp_l[0] + i])
print(' '.join(l))


def swaping(list2, q, b, e, t):
	k = e - b
	for i in range(k):
		(list2[b + i], list2[t + i]) = (list2[t + i], list2[b + i])
num = int(input())
list2 = input().split()
q = int(input())
for i in range(q):
	(b, e, t) = map(int, input().split())
	swaping(list2, q, b, e, t)
print(' '.join(list2))


n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
for i in range(q):
	(b, e, t) = list(map(int, input().split(' ')))
	for k in range(e - b):
		(a[b + k], a[t + k]) = (a[t + k], a[b + k])
print(' '.join(list(map(str, a))))


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		(A[b + k], A[t + k]) = (A[t + k], A[b + k])
print(*A)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for j in range(q):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		aa = a[b + k]
		a[b + k] = a[t + k]
		a[t + k] = aa
print(a[0], end='')
for aa in a[1:]:
	print(' {}'.format(aa), end='')
print()


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		(a[t + k], a[b + k]) = (a[b + k], a[t + k])
print(*a)


from collections import deque
import sys
input = sys.stdin.readline

def main():
	n1 = int(input())
	l1 = list(map(int, input().split()))
	for i in range(int(input())):
		(b, e, t) = map(int, input().split())
		for k in range(e - b):
			(l1[k + b], l1[t + k]) = (l1[t + k], l1[k + b])
	print(' '.join(map(str, l1)))
main()


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, t) = map(int, input().split())
	s = t + e - b
	if t > b:
		a = a[:b] + a[t:s] + a[e:t] + a[b:e] + a[s:]
	else:
		a = a[:t] + a[b:e] + a[s:b] + a[t:s] + a[e:]
print(*a)


n = input()
l = list(map(int, input().split()))
n = int(input())
for i in range(n):
	(b, e, t) = map(int, input().split())
	l1 = l[b:e]
	l2 = l[t:t + e - b]
	l[b:e] = l2
	l[t:t + e - b] = l1
l3 = map(str, l)
print(' '.join(map(str, l3)))


def main():
	n = int(input())
	seq = [int(a) for a in input().split()]
	q = int(input())
	for _ in range(q):
		(b, e, t) = map(int, input().split())
		for k in range(e - b):
			tmp = seq[t + k]
			seq[t + k] = seq[b + k]
			seq[b + k] = tmp
	print(*seq)
main()


n = input()
A = list(input().split())
for i in range(int(input())):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		(A[b + k], A[t + k]) = (A[t + k], A[b + k])
print(*A, sep=' ')


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		(a[b + k], a[t + k]) = (a[t + k], a[b + k])
print(*a)


n = int(input())
L = [int(x) for x in input().split()]
n = int(input())
for _ in range(n):
	(b, e, t) = [int(x) for x in input().split()]
	(L[b:e], L[t:t + e - b]) = (L[t:t + e - b], L[b:e])
print(*L)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		(a[b + k], a[t + k]) = (a[t + k], a[b + k])
print(*a)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, t) = map(int, input().split())
	if b < t:
		a = a[:b] + a[t:t + e - b] + a[e:t] + a[b:e] + a[t + e - b:]
	else:
		a = a[:t] + a[b:e] + a[t + e - b:b] + a[t:t + e - b] + a[e:]
print(*a)


def swapRange(A, b, e, t):
	for k in range(e - b):
		(A[b + k], A[t + k]) = (A[t + k], A[b + k])
	return A
n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	query = list(map(int, input().split()))
	A = swapRange(A, query[0], query[1], query[2])
print(' '.join(map(str, A)))


def swap_range(li, b, e, t):
	for k in range(e - b):
		(li[b + k], li[t + k]) = (li[t + k], li[b + k])

def run():
	n = int(input())
	li = input().split()
	assert n == len(li)
	q = int(input())
	for _ in range(q):
		(b, e, t) = [int(x) for x in input().split()]
		swap_range(li, b, e, t)
	print(' '.join(li))
run()


num_a = int(input())
a = list(map(lambda x: int(x), input().split()))
num_query = int(input())
for _ in range(num_query):
	(begin, end, t) = map(lambda x: int(x), input().split())
	for (i, idx) in enumerate(range(begin, end)):
		(a[idx], a[t + i]) = (a[t + i], a[idx])
print(' '.join([str(elem) for elem in a]))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		tmp = a[b + k]
		a[b + k] = a[t + k]
		a[t + k] = tmp
print(*a)


n = int(input())
s = list(map(int, input().split()))
m = int(input())
for i in range(m):
	(b, e, t) = map(int, input().split())
	for k in range(e - b):
		(s[b + k], s[t + k]) = (s[t + k], s[b + k])
print(*s)


def solve():
	from sys import stdin
	f_i = stdin
	n = f_i.readline()
	A = f_i.readline().split()
	q = int(f_i.readline())
	for i in range(q):
		(b, e, t) = map(int, f_i.readline().split())
		w = e - b
		if b < t:
			A = A[:b] + A[t:t + w] + A[b + w:t] + A[b:b + w] + A[t + w:]
		else:
			A = A[:t] + A[b:b + w] + A[t + w:b] + A[t:t + w] + A[b + w:]
	print(' '.join(A))
solve()


def main():
	n = int(input())
	A = list(map(int, input().split()))
	m = int(input())
	for _ in range(m):
		(a, b, c) = map(int, input().split())
		(A[a:b], A[c:c + (b - a)]) = (A[c:c + (b - a)], A[a:b])
	print(' '.join(map(str, A)))
main()


readline = open(0).readline
N = int(readline())
(*A,) = map(int, readline().split())
Q = int(readline())
for _ in range(Q):
	(b, e, t) = map(int, readline().split())
	for k in range(e - b):
		(A[b + k], A[t + k]) = (A[t + k], A[b + k])
print(*A)


input()
nums = list(map(int, input().split(' ')))
n = int(input())
for _ in range(n):
	(f, m, l) = list(map(int, input().split(' ')))
	m = m - f
	if f > l:
		(f, l) = (l, f)
	sb_1 = list(nums[f:f + m])
	sb_2 = list(nums[l:l + m])
	nums = nums[:f] + sb_2 + nums[f + m:l] + sb_1 + nums[l + m:]
print(' '.join(map(str, nums)))


n = int(input())
arr = input().split()
nq = int(input())
for i in range(nq):
	(begin, end, tgt) = map(int, input().split())
	length = end - begin
	if begin < tgt:
		arr = arr[:begin] + arr[tgt:tgt + length] + arr[end:tgt] + arr[begin:end] + arr[tgt + length:]
	else:
		arr = arr[:tgt] + arr[begin:end] + arr[tgt + length:begin] + arr[tgt:tgt + length] + arr[end:]
print(*arr)


def partial_swap(origin, begin, end, begin2):
	for i in range(end - begin):
		(origin[begin + i], origin[begin2 + i]) = (origin[begin2 + i], origin[begin + i])
	return origin
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for i in range(Q):
	(b, e, t) = map(int, input().split())
	A = partial_swap(A, b, e, t)
print(' '.join(map(str, A)))


from copy import deepcopy
n = int(input())
a = list(map(int, input().split()))
for i in range(int(input())):
	(b, e, t) = map(int, input().split())
	tmp = deepcopy(a)
	for k in range(e - b):
		a[t + k] = tmp[b + k]
		a[b + k] = tmp[t + k]
print(*a)