题目描述

给出长度为$n$的正整数序列$a$，共有$q$次修改。

每次修改给出$x,y$ ，表示将序列中所有权值为$x$的元素均修改为$y$。

例如对序列{${1,2,1,3,4}$}执行修改$1,3$序列会变成{${3,2,3,3,4}$}。

每次修改后，你需要输出当前序列中所有元素之和为多少。

输入格式

第一行一个正整数$n$表示序列长度。

第二行包含$n$个元素，表示序列$a$ 。

第三行包含一个正整数$q$。

之后$q$行，每行给出两个正整数$x,y$表示一次修改，保证$x\neq{y}$。

输出格式

对于每次修改，输出一行，表示答案

样例

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

11
12
16

样例1解释： 第一次修改后数据为{${2,2,3,4}$}, 第二次修改后数据为{${2,2,4,4}$}, 第三次修改后数据为{${4,4,4,4}$}.

2
1 2
3
1 100
2 100
100 1000

102
200
2000

数据范围

对于30%的数据，$1\leq{n,q}\leq{10^3},1\leq{a_i,x_i,y_i}\leq{10^3}$ 对于60%的数据，$1\leq{n,q}\leq{10^5},1\leq{a_i,x_i,y_i}\leq{10^3}$ 对于100%的数据，$1\leq{n,q}\leq{10^5},1\leq{a_i,x_i,y_i}\leq{10^5}$