题目描述

给出由 $N$ 个正整数组成的序列 $A$，接着执行 $Q$ 次替换。每次把当前序列中所有等于 $B_i$ 的元素替换为 $C_i$，并输出替换后的所有元素之和。操作会影响后续的序列。

输入格式

第一行 $N$；第二行 $N$ 个整数 $A_i$；第三行 $Q$；随后 $Q$ 行，每行两个整数 $B_i,C_i$。

输出格式

每次替换后输出一行，包含当前序列元素的总和。

数据范围

$1\le N,Q,A_i,B_i,C_i\le 10^5$；$B_i\ne C_i$。总和可能超过 32 位有符号整数范围。

输入输出样例

样例 1

1
1
1
1 2

2

样例 2

1
4
1
2 3

4

样例 3

3
2 2 5
2
2 5
5 9

15
27

样例 4

3
3 3 8
2
3 8
8 3

24
9

样例 5

3
1 1 2
3
1 2
1 3
2 4

6
6
12

样例 6

2
1 100000
2
1 100000
100000 1

200000
2

样例 7

4
2 4 6 8
3
2 4
6 4
8 4

22
20
16