問題文

あなたは、$N$ 個の正整数 $A_{1}, A_{2}, \\cdots, A_{N}$ からなる数列 $A$ を持っています。

あなたは、これから以下の操作を $Q$ 回、続けて行います。

• $i$ 回目の操作では、値が $B_{i}$ である要素すべてを $C_{i}$ に置き換えます。

すべての $i$ $(1 \\leq i \\leq Q)$ に対して、$i$ 回目の操作が行われた後の数列 $A$ のすべての要素の和、$S_{i}$ を求めてください。

制約

• 入力は全て整数
• $1 \\leq N, Q, A_{i}, B_{i}, C_{i} \\leq 10^{5}$
• $B_{i} \\neq C_{i}$

入力

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

$N$ $A_{1}$ $A_{2}$ $\\cdots$ $A_{N}$ $Q$ $B_{1}$ $C_{1}$ $B_{2}$ $C_{2}$ $\\vdots$ $B_{Q}$ $C_{Q}$

出力

$Q$ 個の整数 $S_{i}$ を以下の形式で標準出力に出力せよ。

$S_{1}$ $S_{2}$ $\\vdots$ $S_{Q}$

$S_{i}$ は $32$ ビット整数に収まらない可能性があることに注意せよ。

入力例 1

4
1 2 3 4
3
1 2
3 4
2 4

出力例 1

11
12
16

はじめ、数列 $A$ は $1,2,3,4$ です。

各操作後、 数列 $A$ は以下のようになります。

• $2, 2, 3, 4$
• $2, 2, 4, 4$
• $4, 4, 4, 4$

入力例 2

4
1 1 1 1
3
1 2
2 1
3 5

出力例 2

8
4
4

数列 $A$ に 要素の値が $B_{i}$ であるものが $1$ つも含まれていない可能性もあることに注意してください。

入力例 3

2
1 2
3
1 100
2 100
100 1000

出力例 3

102
200
2000