Občas je tým najdôležitejším v živote správne sa narodiť – a farmárovi Bohdanovi sa to nie tak celkom podarilo. Tak ako jeho rodičia, súrodenci, susedia a krajania, aj Bohdan vyznáva lokálne náboženstvo, ktorého bohovia sú známi tým, že sú tak trochu mimo. No dobre, nalejme si čistého vína… sú proste úplne šialení.

Tak napríklad: farmárom trvalo niekoľko generácií, kým prišli na to, akým presným spôsobom sa majú k bohom modliť, aby tí pochopili, že ich žiadajú o dážď, ktorý by zavlažil ich úrodu… a že v tom daždi má pršať voda, a nie piesok, žaby, kobylky alebo traktory. Podrobnosti správneho rituálu pre stručnosť zadania vynecháme, ale zrejme je jeho podstatnou časťou stojka na hlave s rukami namierenými do správnych svetových strán… pretože vždy keď zaprší, stane sa to iba na úzkom páse poľa. Mohli by ste sa pýtať, prečo by to malo dávať zmysel. Bohdan už sa radšej nepýta.

Asi teda nikoho neprekvapí, že Bohdan, ako každý v okolí, mešká s odvádzaním daní zo svojej úrody – nie je ľahké byť farmárom, keď vaša pšenica rastie každý deň iba na malom pásiku poľa, a všade inde smutne čaká na závlahu. Preto sa rozhodol, že raz za čas proste zožne kúsok poľa, ktorý už stihol narásť dostatočne, namiesto toho, aby čakal celú sezónu a nakoniec zožal celé pole naraz.

Výborne, takže teraz má okrem meškajúcich daní ešte aj poriadny zmätok v tom, koľko pšenice mu zostáva na ktorých kúskoch poľa… Pomôžte mu!

Úloha

Pole tvorí mriežka rozmerov $s \times v$, na začiatku je všade nulové množstvo pšenice. Občas sa stáva, že zaprší na každé políčko určitého riadku alebo stĺpca, a pšenica na daných políčkach vyrastie o nejaký počet jednotiek. Tiež sa stáva, že Bohdan pšenicu na nejakom (práve jednom) políčku zožne. Vtedy ho zaujíma, koľko pšenice z daného políčka dostane.

Formát vstupu a výstupu

Na prvom riadku dostanete zadané prirodzené čísla $s$ (šírku mriežky), $v$ (výšku mriežky) a $q$ (počet dotazov) oddelené medzerami.

Nasleduje $q$ riadkov, každý popisuje jednu udalosť:

• | x j – zaprší na každé políčko v stĺpci $1 \leq x \leq s$, pšenica na nich vyrastie o $1 \leq j \leq 10^9$ jednotiek,
• - y j – zaprší na každé políčko v riadku $1 \leq y \leq v$, pšenica na nich vyrastie o $1 \leq j \leq 10^9$ jednotiek,
• ? x y – Bohdan zožne všetku pšenicu na políčku v stĺpci $x$ a riadku $y$ – a zaujíma ho, koľko jej tým získa.

Pre každú udalosť typu ? odpovedzte jedným číslom – množstvom zožatej pšenice z daného políčka – na samostatnom riadku. Na udalosti typu ? musíte odpovedať online – teda ďalší kúsok vstupu dostanete až potom, čo odpoviete.

Existujú štyri testovacie sady, vo všetkých platí $1 \leq s, v \leq 10^6$ a $1 \leq q \leq 10^5$. V jednotlivých sadách však platia nasledovné dodatočné obmedzenia:

• V prvej sade platí, že $s, v \leq 1000$ a $q \leq 100$.
• V druhej sade platí, že $s = 1$.
• V tretej sade platí, že Bohdan nikdy nebude žať viackrát v tom istom stĺpci ani v tom istom riadku.

Vypisovanie výstupu v online úlohách

Odporúčame zavolať funkciu flush po každom vypísanom riadku, aby program nečakal, kým sa operačný systém rozhodne vyprázdniť zásobník štandardného výstupu (čo sa kvôli efektivite deje menej často, než by bolo pre túto úlohu vhodné). V C++ môžete zavolať std::cout.flush(), alebo jednoducho vypisovať nové riadky pomocou std::endl namiesto \n. V Pythone stačí pridať argument funkcii print(..., flush=True).

Pokiaľ váš program odpovie príliš malým počtom riadkov, dostane ako odpoveď TLE – Prekročený časový limit. Pokiaľ bude riadkov príliš veľa, zobrazí sa vám PRV – Chybný formát.

Príklady

5 5 4
- 1 5
| 2 7
? 2 1
? 2 2

12
7

Do riadku $1$ najskôr zaprší $5$ jednotiek dažďa, potom do stĺpca $2$ zaprší $7$ jednotiek. Na políčku $2,1$ teda narástlo $12$ jednotiek pšenice, na políčku $2,2$ ale iba $7$ jednotiek.

5 5 4
- 1 5
? 2 1
| 2 7
? 2 1

5
7

Keďže políčko $2,1$ zožne Bohdan už po prvom daždi, po druhom daždi z neho získa už iba pšenicu, ktorá narástla medzitým.