A távoli Japánban nagyszámú bűnözőcsoport tevékenykedik. Ezek a jakuza klánok. E bandák tagjai a jakuzák rettegéssel töltik el környezetüket. Tokióban, japán fővárosában éppen hatalmi harc folyik a jakuzák között. A rettegett és félelmetes bűnözők közül legerősebb éppen Momó, aki egész Tokióban át szeretné venni a hatalmat.

Tokiót elképzelhetjük egy \(M\times N\) méretű mátrixként. Momó első nap elfoglal egy (tetszőleges) mezőt ezen a mátrixon. Minden következő nap elfoglalhatja bármelyik, a már elfoglalt mezővel szomszédos mezőt. Két mező szomszédos, ha van közös oldaluk. Mivel Momó nagyon veszélyes bűnöző, nincs olyan mező, amelyet egy nap alatt ne tudna elfoglalni, vagyis \(MN\) nap alatt egész Tokió az övé lesz.

Az igaz, hogy őt egyetlen jakuza sem tudja legyőzni, de van valami ami igen: a saját babonasága. Tulajdonában van egy térkép Tokióról, ahol minden mezőre ráírt egy számot \(1\)-től \(MN\)-ig úgy, hogy minden számot csak egyszer használt fel. Úgy véli, egyetlen módja annak, hogy elfoglalja Tokiót, ha épp az \(i\)-edik napon foglalja el a mezőt, amelyre az \(i\) számot írta. Mivel hangulata nagyon változó, a térképen a számokat \(Q\) -szor megváltoztatja úgy, hogy felcseréli valamely két mezőn a számokat. Feladatotok az, hogy a térkép minden \(Q+1\) állapotára (a kezdetire és minden változtatás után) meghatározzátok, Momó elérheti-e a célját!

Bemenet

A szabványos bement első sorában három természetes szám \(N,M,Q\) állnak (Momó Tokió térképének dimenziói, és a végrehajtott változtatások száma). A soron következő \(N\) sor minden \(i\)-edik sorában \(M\) természetes szám áll, ahol a \(j\)-edik érték, az \(A_{ij}\) az a szám, amelyik kezdetben az \((i,j)\) mezőn áll Momó térképén. A következő \(Q\) sor minden \(i\)-edik sorában \(4\) egész szám, \(xa\), \(ya\), \(xb\), \(yb\) , áll, amelyek azt adják meg, hogy az \(i\)-edik cserénél az \((xa,ya)\) és \((xb,yb)\) mezők értékeit felcseréljük.

Kimenet

A szabványos kimeneten kiíratni \(Q+1\) sort: az \(i\) - edik sorban kiíratni azt hogy DA , ha Momó eltudja foglalni Tokiót a térkép \(i\)-edik állapotában, vagy azt, hogy NE ellenkező esetben!

Korlátozások

• \(1 \leq N\cdot M\leq 300.000\)
• \(1 \leq Q\leq 300.000\)
• \(1 \leq A_{ij} \leq NM\)
• Minden érték \(1\)-től \(NM\)-ig csak egyszer fordul elő az \(A_{ij}\) sorozatban.

Ezenkívül minden \(Q\) lekérdezésre (állapotra) érvényes:

• \(1 \leq x_a,x_b \leq N\)
• \(1 \leq y_a,y_b \leq M\)
• \((x_a,y_a)\neq(x_b,y_b)\)

Alfeladatok

1. (11 pont) \(N=1\), \(Q\leq200\)
2. (17 pont) \(Q\leq200\)
3. (34 pont) \(N=1\)
4. (38 pont) Nincsenek külön korlátozások.

Példák

1. példa

Bemenet

3 3 1
1 2 3
4 5 6
7 8 9
1 2 2 2

Kimenet

DA
NE

Magyarázat

Az első nap Momó elfoglalja az \((1,1)\) mezőt. A következő napokon elfoglalja az \((1,2)\), \((1,3)\), \((2,1)\), \((2,2)\), \((2,3)\), \((3,1)\), \((3,2)\), \((3,3)\) mezőket, melyek szomszédosak az \((1,1)\), \((1,1)\), \((1,1)\), \((1,2)\), \((1,3)\), \((2,1)\), \((2,2)\), \((2,3)\) mezőkkel, melyeket már korábban elfoglalt. A változtatás után azonban az \(1\) jelzésű mező elfoglalása után a következő lépésben már nem tudja elfoglalni a \(2\) számú mezőt.