D2 - Hra spinov ‼

Možno ste sa počuli o projektoch, kde iba pomocou osvetlenia izieb internátu vytvorili študenti obrazec či dokonca animáciu.
Protagonisti tejto úlohy sa rozhodli ísť do extrému a namiesto izieb sa rozhodli meniť spin elektrónov v atómoch uložených v perfektnej dvojrozmernej mriežke. Museli však urobiť mnoho kompromisov a naraz vedia zmeniť len riadky alebo stĺpce ako celky, resp. aj niekoľko riadkov/stĺpcov naraz (napríklad 3. - 5. riadok). Teda ak v invertovanom riadku mal jeden elektrón spin -1/2, tak bude mať spin +1/2 a naopak, pričom stavy jednotlivých atómov sú nezávislé (tá istá operácia môže spin jedného atómu riadka "zvýšiť" a iný "znížiť).
Aktuálnu funkčnosť systému by chceli otestovať, no úrad pre prevenciu časopriestorových anomálií sa obáva, že vysoká koncentrácia záporných spinov na malej ploche môže mať neblahé následky a vyžaduje, aby mohol komisár v ľubovoľný okamih skontrolovať počet atómov so záporným spinom v ním zvolenom bloku, čo vzhľadom na mohutnosť mriečky nie je v ľudských silách a ani ich vlastný algoritmus nebol na počítači dosť rýchly. Pomôžte nešťastným študentom poraziť byrokraciu.

Úloha

Na začiatku sú majú všetky atómy mriežky s R riadkami a S stĺpcami kladný spin. Následne sa aplikujú inštrukcie:

1. Invertuj spin na riadkoch od A po B (vrátane)
2. Invertuj spin na stĺpcoch od A po B (vrátane)
3. Zisti počet atómov so záporným spinom v bloku na riadku od A po B, na stĺpcoch od C po D (vrátane) {obdĺžnik od [A,C] po [B,D]}

Vstup

V prvom riadku súboru sa nachádzajú prirodzené čísla R, S a Q.

Nasleduje Q riadkov, každý nesie samostatnú inštrukciu:

1. R A B
2. S C D
3. Z A B C D

1 ≤ A ≤ B ≤ R ≤ 1 000 000
1 ≤ C ≤ D ≤ S ≤ 1 000 000
1 ≤ Q ≤ 100 000

Pre zaujímavosť, zrnko kuchynskej soli má podobné "rozmery", navyše má ešte tretí rozmer. (~1.2*10¹⁸ atómov)

Výstup

Výstupom programu je pre každú inštrukciu typu 3 riadok s číslom určujúcim počet relevantných (ležiacich v danom bloku) atómov so záporným spinom v čase otázky.

Príklad

Vstup:

4 5 6
Q 1 4 1 5
R 2 2
S 3 3
Q 1 3 1 3
R 1 3
Q 1 4 1 5

Výstup:

0
4
10