Se dă un șir a cu N elemente, numerotate de la 1 la N. Se vor efectua M operații asupra șirului:

• + x y z - Se adună z la elementele din intervalul [x y]
• = x y z - Elementele din intervalul [x y] devin egale cu z
• R x y - Elementele din intervalul [x y] se inversează (a[x] devine a[y], a[x+1] devine a[y-1], ... , a[y] devine a[x])
• D x - Elementul de pe poziția x se șterge, a[1...n] devine a[1...x-1] ∪ a[x+1...n]
• I x z- Se adaugă elementul z pe poziția x, a[1...n] devine a[1...x-1] ∪ z ∪ a[x...n]
• Q x y - Se cere suma elementelor din intervalul [x y]

Să se răspundă tuturor interogărilor de tip Q iar la finalul interogărilor să se printeze șirul a.

Date de intrare

Pe prima linie se citesc N și M. Pe a doua linie se citesc N numere, elementele lui a. Pe următoarele M linii se citesc interogările, după formatul de mai sus.

Date de ieșire

Se va afișa pe câte o linie răspunsul interogărilor Q. Se va afișa pe ultima linie șirul final a, separat prin spații.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ M ≤ 200 000
• Se vor citi doar numere nenule $≤ 10^9$ și rezultatul unei interogări va fi $≤ 10^{18}$.
• Se garantează că operațiile se vor face pe elemente ale lui a care există în acel moment.
• Se garantează că a nu va avea mai mult de N elemente în orice moment.

Exemplu

stdin

5 11
1 2 3 4 5
Q 2 4
+ 1 3 1
Q 2 4
= 4 5 1
Q 2 4
R 1 3
Q 2 4
D 2
Q 2 4
I 3 5
Q 2 4

stdout

9
11
8
6
4
8
4 2 5 1 1