Problem G
Bokföring

Ekonomen Erika har tagit fram en modell för att undersöka hur ekonomisk ojämlikhet uppstår i samhället. Modellen börjar med att ett antal personer har lika mycket pengar. Därefter ändras stegvis hur mycket pengar personerna har, på något komplicerat sätt.

Erika har kört en simulering en massa gånger för att se om modellen fungerar. Tyvärr går simuleringen segt, det tar alldeles för lång tid att hålla koll på hur mycket pengar alla människor har. Hon skulle behöva hjälp av en algoritmexpert.

Du får givet två heltal $N$ och $Q$. Detta innebär att simuleringen består av $N$ personer som alla har ett kapital av $0$ kronor till att börja med. Därefter sker $Q$ händelser. Det finns tre typer av händelser:

1. En händelse av typ “SET” betyder att den $i$:te personens kapital sätts till något givet tal $x$.

2. En händelse av typ “RESTART” betyder simuleringen startar om, så alla personers kapital sätts till något givet tal $x$.

3. En händelse av typ “PRINT” betyder att du ska skriva ut den $i$:te personens kapital.

Skriv ett program som tar hand om händelserna.

Indata

Den första raden innehåller två tal $N$ och $Q$ ($1 \leq N \leq 10^6$, $1 \leq Q \leq 2 \cdot 10^5$). Därefter följer $Q$ rader, som var och en börjar med en sträng som är antingen “SET”, “RESTART”, eller “PRINT”. Det är garanterat att det finns minst en händelse av typen “PRINT”.

Om strängen är “SET” så följer två heltal $i$ och $x$ ($1 \leq i \leq N$, $0 \leq x \leq 10^4$). Om strängen är “RESTART” så följer ett heltal $x$ ($0 \leq x \leq 10^4$). Om strängen är “PRINT” så följer ett heltal $i$ ($1 \leq i \leq N$).

Utdata

För varje händelse av typen “PRINT”, skriv ut den $i$:te personens kapital på en rad.

3 5
SET 1 7
PRINT 1
PRINT 2
RESTART 33
PRINT 1

7
0
33

5 7
RESTART 5
SET 3 7
PRINT 1
PRINT 2
PRINT 3
PRINT 4
PRINT 5

5
5
7
5
5