A warehouse robot rearranges a row of n storage bins (each holding a distinct or repeated bin ID) using its onboard controller, which has no spare register to use as a temporary variable. It performs every swap with the classic three-step XOR trick:

a ^= b
b ^= a
a ^= b

The controller is given a sequence of q swap instructions, each naming two 0-indexed bin positions i and j (possibly i = j, meaning "swap a bin with itself" — a no-op that a careless XOR-trick implementation could corrupt to zero, since i = j means both names refer to the same physical register). Applying the trick to a register with itself must leave its value unchanged.

Apply all q instructions in order, then print the final row of bin IDs.

Input format

Line 1: an integer n. Line 2: n space-separated integers, the initial bin IDs. Line 3: an integer q. Next q lines: two integers i j (0-indexed positions to swap), one pair per line.

Output format

n space-separated integers: the bin IDs after all q swaps, in final left-to-right order.

Constraints

• 1 ≤ n ≤ 1000
• 0 ≤ bin ID ≤ 1,000,000,000
• 0 ≤ q ≤ 1000
• 0 ≤ i, j < n

4
10 20 30 40
2
0 3
1 1

40 20 30 10

3
5 5 9
1
0 1

5 5 9