Inflation

Οι κάτοικοι της νότιας Σουηδίας είναι γνωστό ότι τρώνε πολύ φαλάφελ. Η τιμή του φαλάφελ είναι εξαιρετικά ευμετάβλητη και ο καλύτερος τρόπος για να αναλύσει κανείς την κατάσταση της οικονομίας είναι να πηγαίνει κάθε μέρα στο ίδιο κατάστημα φαλάφελ και να προσθέτει όλες τις τιμές του μενού.

Ένα εστιατόριο με φαλάφελ έχει ~N~ διαφορετικά πιάτα στο μενού του. Το ~i~-οστό πιάτο έχει τιμή ~p_i~.

Κάθε μέρα συμβαίνει ένα από τα ακόλουθα γεγονότα:

• ΠΛΗΘΩΡΙΣΜΟΣ ~x~: Ο ακέραιος ~x~ προστίθεται σε όλες τις τιμές.
• ΑΝΑΘΕΣΗ ~x~ ~y~: Σε κάθε πιάτο με τιμή ~x~ ορίζεται νέα τιμή ~y~.

Η δουλειά σας είναι να επεξεργαστείτε ~Q~ ημέρες και μετά από κάθε ημέρα να εκτυπώσετε το άθροισμα όλων των τιμών ~p_i~.

Είσοδος

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό ~N~, τον αριθμό των πιάτων.

Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~p_1~, ~p_2~, ~\cdots~, ~p_N~.

Η τρίτη γραμμή περιέχει έναν ακέραιο ~Q~, τον αριθμό των ημερών.

Οι επόμενες ~Q~ γραμμές περιέχουν μια συμβολοσειρά ~s~ ακολουθούμενη από έναν ή δύο ακέραιους αριθμούς.

Εάν το ~s~ είναι ΠΛΗΘΩΡΙΣΜΟΣ, τότε ακολουθεί ένας ακέραιος ~x~. Αυτό σημαίνει ότι το ~x~ προστίθεται σε όλες τις τιμές αυτής της ημέρας.

Εάν ~s~ είναι ΑΝΑΘΕΣΗ, τότε ακολουθούν δύο ακέραιοι ~x~ και ~y~. Αυτό σημαίνει ότι όλα τα πιάτα με τιμή ~x~ παίρνουν την τιμή ~y~ αυτή την ημέρα.

Έξοδος

Εκτυπώστε ~Q~ γραμμές, το άθροισμα όλων των τιμών ~p_i~ μετά από κάθε ημέρα.

Περιορισμοί

• ~1 \le N \le 3 \cdot 10^5~
• ~1 \le p_i \le 10^6~ (για κάθε ~1 \le i \le N~)
• ~1 \le Q \le 10^5~
• ~1 \le x, y \le 10^6~ για όλες τις ημέρες.

Σημείωση: Η απάντηση μπορεί να μην χωράει σε έναν ακέραιο ~32~-bit, οπότε προσέξτε τις υπερχειλίσεις αν χρησιμοποιείτε C++.

Η λύση σας θα δοκιμαστεί σε ένα σύνολο ομάδων δοκιμών, καθεμία από τις οποίες αξίζει έναν αριθμό βαθμών. Κάθε ομάδα δοκιμών περιέχει ένα σύνολο δοκιμαστικών περιπτώσεων. Για να λάβετε τους πόντους για μια ομάδα δοκιμών πρέπει να λύσετε όλες τις δοκιμαστικές περιπτώσεις της ομάδας.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	14	~N = 1~
2	28	~N, Q, p_i, x, y \le 100~
3	19	Υπάρχουν ενέργειες μόνο με ΠΛΗΘΩΡΙΣΜΟ.
4	23	Υπάρχουν ενέργειες μόνο με ΑΝΑΘΕΣΗ.
5	16	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

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

output

16
14
14
34
14
5

Επεξήγηση του 1ου παραδείγματος:

Η εικόνα αυτή αντιστοιχεί στις δύο πρώτες ημέρες του παραδείγματος ~1~. Σημειώστε ότι το άθροισμα των τιμών μετά την πρώτη ημέρα είναι ~16~, οπότε ο πρώτος ακέραιος αριθμός στην έξοδο είναι ~16~.

///ΕΙΚΟΝΑ///

input

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

output

6
6
12
8
6