Background

Day 1 Problem A.

The statement is translated from EGOI2023 inflation.

Problem Description

As everyone knows, people in southern Sweden often eat salad sandwiches. The prices of salad sandwiches change a lot, and the best way to analyze the economy is to go to the same salad sandwich shop every day and add up all prices on the menu.

A salad sandwich shop has $N$ different items on its menu. The $i$-th item has price $p_i$.

Each day, one of the following events happens:

• INFLATION x: All prices increase by $x$.
• SET x y: The price of every item whose price is $x$ is changed to $y$.

Your task is to process $Q$ days, and after the end of each day, output the total price of all items.

Input Format

The first line contains an integer $N$, the number of items.

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

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

The next $Q$ lines each contain a string $s$ and one or two integers.

If $s$ is INFLATION, then it is followed by one integer $x$, meaning that all prices increase by $x$ on that day.

If $s$ is SET, then it is followed by two integers $x,y$, meaning that the price of every item whose price is $x$ is changed to $y$.

Output Format

Output $Q$ lines. Each line should contain the total price of all items after the end of that day.

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

16
14
14
34
14
5

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

6
6
12
8
6

Hint

Sample $1$ Explanation

The figure below shows the first two days of sample $1$. Note that after the end of day 1, the total sum of prices is $16$, so the first output integer is $16$.

Constraints

For all testdata, $1\le N\le 3\times 10^5$, $1\le p_i\le 10^6$, $1\le Q\le 10^5$, $1\le x,y\le 10^6$.

• Subtask 1 ($14$ points): $N=1$.
• Subtask 2 ($28$ points): $N,Q,p_i,x,y\le 100$, depends on Subtask 1.
• Subtask 3 ($19$ points): Only INFLATION events.
• Subtask 4 ($23$ points): Only SET events.
• Subtask 5 ($16$ points): No special constraints, depends on Subtasks 2, 3, and 4.

Hint

The answer may not fit in a 32-bit integer. If you use C++, be careful about possible overflow.

Translated by ChatGPT 5