Inflation

Interview

Time limit3sMemory limit1024 MB

Summary

Given N dish prices, apply Q events (add x to every price, or set each price equal to x to y) and print the price sum after each event.

Level: Medium5 of 10
Topics: Hash map, Implementation
Solved: No attempts yet

Problem

People in southern Sweden are known to eat falafel a lot. The price of falafel changes often, and the best way to analyze the state of the economy is to visit the same falafel place every day and add up all the prices on its menu.

A falafel place has $N$ different dishes on its menu. The $i$ th dish has price $p_i$ .

Every day, one of the following events happens:

INFLATION x: The integer $x$ is added to all prices.
SET x y: Every dish with price $x$ gets its price set to $y$ .

Your task is to process $Q$ days, and after each day print the sum of all prices $p_i$ .

Input

The first line contains one integer $N$ , the number of dishes.

The second line contains $N$ integers $p_1, p_2, \ldots, p_N$ .

The third line contains one integer $Q$ , the number of days.

The following $Q$ lines each contain a string $s$ followed by either one or two integers.

If $s$ is INFLATION, then one integer $x$ follows. This means that $x$ is added to all prices on this day.

If $s$ is SET, then two integers $x$ and $y$ follow. This means that all dishes with price $x$ get their price set to $y$ on this day.

Output

Print $Q$ lines. Line $k$ contains the sum of all prices $p_i$ after day $k$ .

Constraints

$1 \leq N \leq 3 \cdot 10^5$ .
$1 \leq p_i \leq 10^6$ for each $i$ such that $1 \leq i \leq N$ .
$1 \leq Q \leq 10^5$ .
$1 \leq x, y \leq 10^6$ for all days.

Note: The answer may not fit in a $32$ -bit integer, so be careful about overflow if you use C++.

Hint

This figure corresponds to the first two days of sample $1$ . The sum of prices after the first day is $16$ , so the first integer in the output is $16$ .

Examples2

Example 1

Input

5
2 1 1 2 5
6
INFLATION 1
SET 3 2
SET 5 2
INFLATION 4
SET 6 1
SET 10 1

Expected output

Example 2

Input

3
1 4 1
5
SET 1 1
SET 3 4
INFLATION 2
SET 3 1
SET 6 4

Expected output