Tehtävänäsi on ylläpitää $n$ luvun taulukkoa. Aluksi taulukko on täynnä nollia. Taulukkoon tehdään seuraavanlaisia kyselyjä:

• S: laske taulukon yhtenäisen välin summa modulo $2^{64}$
• R: käännä taulukon yhtenäinen väli ympäri
• A: lisää taulukon yhtenäisellä välillä kaikkiin lukuihin annettu arvo

Syöte

Syötteen ensimmäisellä rivillä on luvut $n$ ja $q$, taulukon koko ja kyselyiden lukumäärä. Seuraavat $q$ riviä sisältävät kyselyt. Jokaisella kyselyrivillä on ensin merkki, joka kertoo kyselyn tyypin: S, R tai A. Rivin loppu riippuu kyselytyypistä:

• S: luvut $a$ ja $b$, välin alku- ja loppukohdat ($1\leq a\leq b\leq n$)
• R: luvut $a$ ja $b$, välin alku- ja loppukohdat ($1\leq a\leq b\leq n$)
• A: luvut $a$ ja $b$ ja $d$, välin alku- ja loppukohdat, sekä välin jokaiseen alkioon lisättävä luku, ($1\leq a\leq b\leq n$)

Tuloste

Tulosta jokaista S-kyselyä kohti välin summa modulo $2^{64}$ omalle rivilleen.

Rajat

• $1\leq n\leq 5\cdot 10^5$
• $1\leq q\leq 5\cdot 10^5$
• $1\leq d\leq 10^{12}$

Esimerkki

Syöte:

8 24
R 7 8
R 2 3
A 1 3 66
S 1 5
A 2 4 43
R 1 4
R 5 6
S 3 8
R 4 8
A 1 7 8
S 6 6
R 1 3
A 4 8 91
S 3 7
S 2 3
R 4 8
R 4 8
S 4 4
S 7 8
A 1 6 74
S 1 6
A 6 6 88
A 5 6 13
S 2 4

Tuloste:

198
175
8
447
168
99
256
1026
489