题目描述

あなたは、$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}$ を求めてください。

输入格式

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

$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

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

8
4
4

2
1 2
3
1 100
2 100
100 1000

102
200
2000

提示

制約

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

Sample Explanation 1

はじめ、数列 $A$ は $1,2,3,4$ です。 各操作後、 数列 $A$ は以下のようになります。 - $2,\ 2,\ 3,\ 4$ - $2,\ 2,\ 4,\ 4$ - $4,\ 4,\ 4,\ 4$

Sample Explanation 2

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