aura

Cerință

Iustin și Radu se joacă din nou Clash Royale și în timp ce se jucau, au început să discute despre spellurile pe care le pot folosi. Având suficientă aură după ce au câștigat trofee în loc să se pregătească pentru OJI, le-a venit următoarea idee de problemă:

Se dă un vector cu $n$ numere naturale și $q$ actualizări, care pot fi de două tipuri, după cum urmează:

• $1 \ x \ val$: valoarea de pe poziția $x$ devine egală cu $val$.
• $2 \ val$: toate valorile din șir devin egale cu $val$.

După fiecare operație, trebuie să afișați suma elementelor din șir.

Acum cei doi au văzut că se organizează preOJI așa că s-au decis să propună această problemă aici. Ajută-i să rezolve problema!.

Date de intrare

Pe prima linie a fișierului de intrare aura.in se găsesc două numere întregi, $n$ și $q$.

Pe următoarea linie se găsește șirul de numere de lungime $n$, care conține valori naturale.

Următoarele $q$ linii conțin câte două sau trei numere naturale, în funcție de tipul actualizării.

Date de ieșire

Fișierul de ieșire aura.out va avea $q$ linii, fiecare conținând suma numerelor după primele $i$ operații.

Restricții și precizări

• $1 \leq n, q \leq 200 \ 000$;
• $1 \leq val \leq 1 \ 000 \ 000 \ 000$, unde $val$ este o valoare din șir sau o valoare actualizată.
• Pentru teste în valoare de $20$ de puncte, $1 \leq n, q \leq 1 \ 000$;
• Pentru alte teste în valoare de $20$ de puncte, vor exista cel mult $10$ operații de tip $2$;
• Pentru alte teste în valoare de $40$ de puncte, $1 \leq val \leq 1 \ 000$;

Exemplu

aura.in

6 7
5 4 1 2 3 4
1 2 5
1 5 8
2 5
1 4 3
2 6
1 5 9
1 3 2

aura.out

20
25
30
28
36
39
35

Explicație

După prima operație, șirul va fi $[5, 5, 1, 2, 3, 4]$.
După cea de-a doua operație, șirul va fi $[5, 5, 1, 2, 8, 4]$.
După cea de-a treia operație, șirul va fi $[5, 5, 5, 5, 5, 5]$.
După cea de-a patra operație, șirul va fi $[5, 5, 5, 3, 5, 5]$.
După cea de-a cincea operație, șirul va fi $[6, 6, 6, 6, 6, 6]$.
După cea de-a șasea operație, șirul va fi $[6, 6, 6, 6, 9, 6]$.
După cea de-a șaptea operație, șirul va fi $[6, 6, 2, 6, 9, 6]$.