007 - SWAP

問題

長さ $N$ の数列 $S = \{S_1, S_2, \ldots , S_N \}$ が与えられます。
これから、以下のような $Q$ 回の操作を順に行います。

操作 $j$ $(1 \leq j \leq Q)$ : $S_{A_j}$ の値と $S_{B_j}$ の値を入れ替える。

すべての操作を行った後の $S$ を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$S_1$ $S_2$ $\ldots$ $S_N$
$Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_Q$ $B_Q$

出力

すべての操作を行った後の $S$ の各項を空白区切りで出力せよ。
ただし、以下のことに注意すること。

• 出力の末尾には改行をいれる。
• 余分な空白を出力してはならない。

制約

• $2 \leq N \leq 10^5$
• $-10^9 \leq S_i \leq 10^9$ $(1 \leq i \leq N)$
• $0 \leq Q \leq 10^5$
• $1 \leq A_j, B_j \leq N$ $(A_j \neq B_j)$

入出力例

入力例1

5
1 2 3 4 5
2
2 4
1 5

出力例1

5 4 3 2 1

入力例2

9
6 12 11 5 19 13 16 10 7
4
9 8
2 4
7 5
9 7

出力例2

6 5 11 12 16 13 10 7 19

入力例3

7
3 14 11 18 7 20 14
3
7 1
2 5
3 6

出力例3

14 7 20 18 14 11 3