配点 : $400$ 点

問題文

あなたは、$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$ ビット整数に収まらない可能性があることに注意せよ。

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

11
12
16

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

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

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

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

8
4
4

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

2
1 2
3
1 100
2 100
100 1000

102
200
2000