問題
長さ $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