カードシャッフル

機械技師のエチゼン氏はカード列（順番の定義された2枚以上のカードの並び）を並び替える機械を作った． この機械はカード列をセットすると，以下の手順を M 回繰り返してカード列を並び替える．

1. カード列中の A_{1, 1} 枚目のカードと A_{1, 2} 枚目のカードを交換する．
2. カード列中の A_{2, 1} 枚目のカードと A_{2, 2} 枚目のカードを交換する．
3. …
4. カード列中の A_{L, 1} 枚目のカードと A_{L, 2} 枚目のカードを交換する．

いま，N 枚のカードからなるカード列があり， それらには現在の並び順に C₁, C₂, …, C_N という数値が書かれている． このカード列を機械にセットして並び替えが終わった後，カード列に書かれている数値を並び順にすべて出力するプログラムを作成せよ． ただし，M，L，A_{i, j} (i = 1, 2, …, L; j = 1, 2) は既知とする．

入力

入力は以下の形式で与えれれる．

M L
A_1_1 A_1_2
A_2_1 A_2_2
...
A_L_1 A_L_2
N
C_1
C_2
...
C_N

• 第1行目の M は機械の繰り返し回数 M を与え，L は繰り返しごとの交換回数 L を与える．
• 第2行目から第L+1行目の A_i_1，A_i_2 は 各繰り返し内の i 回目に交換するカードの順番 A_{i, 1}，A_{i, 2} を与える（i = 1, 2, …, L）．
• 第L+2行目の N は並び替えを行うカード列のカードの枚数 N を与える．
• 第L+3行目から第L+N+2行目の C_i は並び替えを行うカード列のカードに書かれた数値 C_i を順に与える（i = 1, 2, …, N）．

制約

• M，L，A_{i, j} (i = 1, 2, …, L; j = 1, 2)，N，C_i (i = 1, 2, …, N) は整数．
• 1 ≤ M ≤ 10⁵
• 1 ≤ L ≤ 10⁶
• 1 ≤ A_{i, j} ≤ N (i = 1, 2, …, L; j = 1, 2)
• A_{i, 1} ≠ A_{i, 2} (i = 1, 2, …, L)
• 2 ≤ N ≤ 10⁴
• 1 ≤ C_i ≤ 10⁴ (i = 1, 2, …, N)

出力

カード列の並び替えが終わった後，カード列に書かれている数値を並び順にすべて出力せよ．

例

入力1:

2 3
1 3
2 4
1 2
4
6
3
10
2

出力1:

3
6
2
10

入力2:

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

出力2:

1
7
6
3
2
8