Sum After Query Update

Each query old new replaces every element of the current array that equals old with new, then outputs the sum after the change. Queries take effect cumulatively; when old=new or old is not currently present, the array does not change.

输入格式

The first line contains n q, the second line contains n integers, followed by q lines of old new. On this site 0≤n,q≤200000, and all array and query values are in −10^9..10^9.

输出格式

Output the sum after each change, one per line in query order, for q lines in total; when q=0, output an empty line.

样例 1

输入：

3 3
1 1 2
1 2
2 2
2 -1

输出：

6
6
-3

样例 2

输入：

1 3
0
3 4
0 0
0 2

输出：

0
0
2

样例 3

输入：

0 0

输出：

样例说明

The outputs of the three public examples are 6 / 6 / -3; 0 / 0 / 2; and an empty line, checked by independent enumeration or direct simulation.