A. Swap by Value
time limit per test
2.5 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

Tyger has an array of $$$n$$$ values, where each integer is between $$$1$$$ and $$$n$$$ inclusive and occurs exactly once. Regyt is unpleased with the arrangement of values, and provides instructions for Tyger to rearrange his array.

Regyt's instructions come in the form of $$$q$$$ queries. Each query requires Tyger to swap the positions of two values, $$$x$$$ and $$$y$$$, in the array. $$$x$$$ and $$$y$$$ refer to values, not indices. To check his work, Tyger would like you to determine the final array!

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, representing the size of the permutation.

The second line contains $$$n$$$ integers, representing the array $$$p_1, \dots, p_n$$$

The next line contains a single integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$, representing the number of queries.

Then, $$$q$$$ lines follow. Each line contains two integers $$$x$$$ and $$$y$$$ $$$(1 \leq x, y \leq n)$$$, representing the values to swap.

Output

Output $$$n$$$ integers, the resulting array after performing all the swaps.

Scoring

In tests worth $$$50$$$ points, it is guaranteed that $$$1 \leq n, q \leq 1000$$$

Example
Input
7
5 2 3 7 4 1 6
4
1 2
6 7
2 5
3 5
Output
2 1 5 6 4 3 7
Note

After each instruction, the array becomes 

5 1 3 7 4 2 6
5 1 3 6 4 2 7
2 1 3 6 4 5 7
2 1 5 6 4 3 7

Credit: RandomChicken