题目描述

你有一个由 $N$ 个正整数组成的序列 $A$: $A_{1}, A_{2}, \\cdots, A_{N}$。

接下来，你将依次执行以下 $Q$ 个操作：

• 在第 $i$ 个操作中，将所有值为 $B_{i}$ 的元素替换为 $C_{i}$。

对于每个 $i$ $(1 \leq i \leq Q)$，找到 $S_{i}$：第 $i$ 个操作后序列 $A$ 中所有元素的和。

约束条件

• 输入中的所有值都是整数。
• $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$。

每次操作后，它变为以下形式：

• $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}$ 的元素。

示例输入3

2
1 2
3
1 100
2 100
100 1000

示例输出3

102
200
2000