1129 - メンバーが入れ替わったアイドルグループ

ストーリー

ei1821は筍派(急進派)である。

長さが$N$の数列$T$が与えられる。
あなたは$Q$回、$X$_i番目にある値と$Y$_i番目にある値を入れ替える。
最終的な数列を出力せよ。

入力

1行目に、数列長Nが与えられる。
2行目以降N行に渡って数列の値T_iが与えられる。
N+1行目に命令数Qが与えられる。
N+2行目以降Q行に渡って入れ替える数字の位置が2つずつ与えられる。

N
T1
T2
...
TN
Q
X1 Y1
X2 Y2
...
XQ YQ

出力

最終的な数列を空白区切りで出力せよ。
なお、行末に不必要な空白が有る場合は間違いとする。
最後の改行を忘れずに。

制約

• 1 ≤ $N$ ≤ 10⁶
• 1 ≤ $Q$ ≤ 10⁶
• 1 ≤ $T$_i ≤ 10e8
• 1 ≤ $X$_i, $Y$_i ≤ $N$

入出力例

例1

入力

5
10 20 30 40 50
3
1 2
1 3
3 5

出力

30 10 50 40 20

一回目の入れ替えで、1番目と2番目の値、10と20の位置が変わる。
二回目の入れ替えで、1番目と3番目の値、20と30の位置が変わる。
三回目の入れ替えで、3番目と5番目の値、20と50の位置が変わる。
よってこのような出力結果となる。
　

例2

入力

3
1830 1804 1807
3
1 3
2 2
3 1

出力

1830 1804 1807

補足

タイトルの元ネタは某氏のTwitter