Problem D
Manhattanstíflur

Mynd fengin af commons.wikimedia.org

Eins og er vel þekkt samanstendur gatnakerfi Manhattan af götum sem liggja frá norðri til suðurs og frá austri til vesturs. Skulum númera göturnar sem liggja frá norðri til suðurs $0, 1, \dots , n$ þar sem $0$ er vestasta slíka gatan. Númerum einnig göturnar frá austri til vesturs með $0, 1, \dots , m$ þar sem $0$ er nyrsta slíka gatan. Þá getum við táknað gatnamót með númerum gatnanna sem mynda mótin, frá $(0, 0)$ til $(n, m)$. Við höfum áhuga á að geta komist frá norðvesturhorninu $(0, 0)$ í suðausturhornið $(n, m)$ með því að ferðast meðfram götunum. Hins vegar er alltaf verið að loka leiðum milli aðlægra gatnamóta vegna framkvæmda eða annarra uppákoma. Getur þú svarað því hvenær slíkar framkvæmdir loka á allar leiðir frá $(0, 0)$ til $(n, m)$?

Inntak

Fyrsta línan inniheldur eina jákvæða heiltölu $q$. Næst kemur lína með tveimur jákvæðum heiltölum $n, m$, fjölda gatna í hvora stefnu. Loks fylgja $q$ línur, hver þeirra með upplýsingar um götubút sem er lokað. Hver lína hefur fjórar heiltölur $x_1, y_1, x_2, y_2$ sem uppfylla $0 \leq x_1, x_2 \leq n$ og $0 \leq y_1, y_2 \leq m$. Þetta merkir að leiðin frá gatnamótunum $(x_1, y_1)$ að gatnamótunum $(x_2, y_2)$ er lokað. Þessi gatnamót eru ávallt aðlæg hvorum öðrum.

Úttak

Ef fyrirspurn númer $i$ lokar á allar leiðir frá $(0, 0)$ til $(n, m)$, prentið $i$. Ef ennþá er hægt að fara frá $(0, 0)$ til $(n, m)$ eftir allar fyrirspurnir, prentið $-1$ í staðinn.

Stigagjöf

4
1 2
0 2 0 1
0 1 1 1
1 0 1 1
0 2 1 2

3

5
3 3
0 0 1 0
0 1 0 2
1 1 1 2
0 2 1 2
2 1 1 1

-1