题目描述

有 $n$ 件物品，一开始第i件物品的价值是 $a_i$。

现在依次进行 $Q$ 次操作，第 $i$ 次操作给出两个整数：$b_i$ 和 $c_i$，表示的意思是：凡是价值等于 $b_i$ 的物品，把它们的价值都变成 $c_i$。

第 $i$ 次操作结束以后，你把要输出当前所有物品的价值的总和。

输入格式

第一行，一个整数 $n$ ( $1 \le n \le 10^5$。

第二行，$n$ 个整数，第 $i$ 个整数是 $a_i$ ( $1 \le a_i \le 10^5$ )。

第三行，一个整数 $Q$ ($1 \le Q \le 10^5$ )。

接下来有 $Q$ 行，第 $i$ 行有两个整数 $b_i$ 和 $c_i$，其中 $b_i \ne c_i$ ($1 \le b_i,c_i \le 10^5$)。

输出格式

共Q行，每行一个整数。

样例

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