Problem Statement

You have a sequence $A$ composed of $N$ positive integers: $A_1,A_2,\cdots ,A_N$.

You will now successively do the following $Q$ operations:

• In the $i$-th operation, you replace every element whose value is $B_i$ with $C_i$.

For each $i$ $(1\le i\le Q)$, find $S_i$: the sum of all elements in $A$ just after the $i$-th operation.

Constraints

• All values in input are integers.
• $1\le N,Q,A_i,B_i,C_i\le {10}^5$
• $B_i\ne C_i$

---

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$Q$
$B_1$ $C_1$