Problem superquery


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 intevalul [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

General info

ID: 79

Upload: liviu

Input: Console Input

Memory limit: 128MB/128MB

Time limit: 1s

Submissions

Special Submissions