Codah ClubExersează. Trimite. Progresează.
Autentificare
Română
#000722

P-OldGrid

Mali Perica poseduje staru matricu LED dioda. To nisu obične LED diode, zapravo mogle bi se nazvati "hiper-diodama", zato što imaju više stanja od samo uključeno/isključeno. Mogu imati jako veliki broj stanja, od kojih svako odgovara celom broju u intervalu od 1 do 100000. Jednoga dana, Perica je odlučio da hoće da se opet igra sa svojim matricom. Primetio je da su se sva stanja na početku podesila na predodredjenu vrednost D, medjutim, pošto je matrica mnogo stara, nemoguće je promeniti stanje mnogih dioda na matrici.


Pericu zanima u svakom momentu, proizvod svih vrednosti stanja dioda unutar nekog pravougaonog podskupa matrice. Nažalost, odavno nije programirao, pa vas je zamolio za pomoć.


Input

U prvom redu standardnog ulaza nalaze se tri cela broja: N (1 <= N <= 50000), Q (1 <= Q <= 50000) i D (1 <= D <= 100000), koji predstavljaju broj LED-ova koje možemo menjati, broj komandi koje ćemo izdati, i početno stanje svake diode u matrici, redom.


Svaki od narednih N redova sadrži dva cela broja xi i yi (1 <= xi, yi <= 100000, 1 <= i <= N), koji predstavljaju koordinate i-te diode čije stanje Perica može da promeni.


U svakom od poslednjih Q redova se nalazi opis jedne komande. Komande mogu biti sledećeg oblika:


SET i x - postaviti vrednost i-te aktivne diode na x;


SWAP i j - zameniti vrednosti i-toj i j-toj aktivnoj diodi;


QUERY x y a b - odrediti proizvod svih vrednosti dioda unutar pravougaonika sa donjim levim temenom (x, y), širinom a i visinom b.


OutputZa svaku komandu tipa QUERY, ispisati traženi proizvod po modulu 1000000007 (10^9 + 7), svaki u zasebnoj liniji standardnog izlaza.

Ulaz:
2 5 5
1 1
2 2
QUERY 1 1 2 2
SET 1 10
QUERY 1 1 2 2
SWAP 1 2
QUERY 1 1 1 1
Izlaz:
625
1250
5
Objašnjenje: Na početku, sve diode u matrici su postavljene na stanje 5. Pošto prvi upit sadrži četiri polja u svom pravougaoniku, traženi proizvod je 5^4 = 625. Nakon što se stanje diode u ćeliji (1,1) postavi na 10, proizvod unutar tog istog pravougaonika postaje 10 * 5^3 = 1250. Nakon zamene mesta vrednostima u ćelijama (1,1) i (2,2), vrednost u ćeliji (1,1) je ponovo 5.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.