Problem T
Þarasöfnun

Mynd eftir Peter Southwood, fengin af Wikimedia Commons

Enn eina ferðina eru tilteknir ónefndir einstaklingar í KFFÍ að reyna að komast í auðveldan pening og höfðu þeir heyrt frá verkfræðingavinum sínum að allt umhverfisvænt og framtíðarlegt fær næga styrki þessa dagana. Með þetta í huga fékk einn þeirra þá hugmynd að smíða þararæktunarvélmenni. Síðar kom auðvitað í ljós að það var ekki alveg jafn einfalt og þeir héldu, sérstaklega þegar þurfti að smala saman verkfræðingum til að smíða sjálft vélmennið. Svo illa gekk þetta að það steingleymdist að forrita vélmennið til að gera það sem það á að gera, allur tíminn fór í annað.

Búið er að koma fyrir mælitækjum í sjónum þar sem þarinn vex, svo eina sem þarf að gera er að koma vélmennið á réttan stað til að sækja þarann þegar boð berast frá mælitækjunum. Ræktarreitinn má líta á sem $C \times R$ reiti með þaraplöntu í hverjum reit. Vélmennið er staðsett í $(0, 0)$ í byrjun og lítum svo á að við byrjum á tíma $0$. Vélmennið getur ferðast um einn reit á sekúndu lárétt, lóðrétt eða skáhallt. Þegar þari er tilbúinn til að sækja skal vélmennið ferðast á þann reit með sem stysta hætti og á ávallt að ferðast skáhallt meðan það borgar sig. Hunsa má tímann sem það tekur vélmennið að sækja þarann þegar hann er kominn á réttan stað. Ávallt skal sækja þarann sem kom fyrst fyrir í inntaki ef fleiri en ein fyrirspurn bíður eftir afgreiðslu. Hins vegar, ef farið er á reit með þara sem bíður við það að fara eitthvert annað skal sækja hann í leiðinni. Ef vélmennið hefur ekkert að gera skal það einfaldlega halda sér kyrrt.

Inntak

Fyrsta línan í inntakinu inniheldur tvær jákvæðar heiltölur $C, R$, fjöldi dálka og raða af reitum á ræktunarsvæðinu. Næsta lína inniheldur eina jákvæða heiltölu $q$, fjölda fyrirspurna. Loks koma $q$ línur, hver með þremur heiltölum $t$, þar sem $0 \leq t \leq 10^{18}$, $x$, þar sem $0 \leq x < C$, og $y$, þar sem $0 \leq y < R$. $t$ er tíminn sem mælingin berst um að þarinn sé tilbúinn og $(x, y)$ er staðsetning þarans. Hver staðsetning kemur mest fyrir einu sinni, $(x, y) \neq (0, 0)$ og tími er í veikt vaxandi röð.

Úttak

Skrifið út tíma og staðsetningu á sama formi og í inntaki hvert sinn sem þara er safnað, í þeirri röð sem þeim er safnað.

Stigagjöf

5 10
1
1 3 6

7 3 6

10 10
4
1 2 6
2 7 7
3 8 8
4 0 8

7 2 6
12 7 7
13 8 8
21 0 8

9 9
4
2 0 6
4 0 5
10 0 8
11 4 4

7 0 5
8 0 6
12 0 8
16 4 4

5 5
3
0 3 4
0 3 3
0 4 3

3 3 3
4 3 4
5 4 3