|
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.
Po mnohých invektívach a ústupkoch stačí, aby mohol komisár v ľubovoľný okamih skontrolovať stav konkrétneho atómu, čo zatiaľ ale projekt študentov nepodporuje.
Pomôžte nešťastným študentom poraziť byrokraciu.
Úloha
Na začiatku sú majú všetky atómy mriežky s X riadkami a Y stĺpcami kladný spin. Následne sa aplikujú inštrukcie:
- Invertuj spin na riadkoch od A po B (vrátane)
- Invertuj spin na stĺpcoch od C po D (vrátane)
- Zisti stav atómu v riadku A, stĺpci C
Vyrobte program, ktorý bude vedieť rýchlo odpovedať na dopyty.
Vstup
V prvom riadku súboru sa nachádzajú prirodzené čísla X, Y a Q.
Nasleduje Q riadkov, každý nesie samostatnú inštrukciu:
- R A B
- S C D
- Q A C
1 ≤ A ≤ B ≤ X ≤ 1 000 000
1 ≤ C ≤ D ≤ Y ≤ 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*1018 atómov)
Výstup
Výstupom programu je pre každú inštrukciu typu 3 riadok jedným znakom - znamienkom spinu daného atómu (+ alebo -).
Príklad
Vstup:
4 5 6
Q 2 3
R 2 2
S 3 3
Q 2 3
R 1 3
Q 2 3
Výstup:
+
+
-
|