Husbygge

문제

Ett antal excentriker från centrala New York har bestämt sig för att de har fått nog av det moderna samhället, och vill flytta därifrån. Tillsammans har de köpt en rektangulär bit mark långt borta, och ska nu bosätta sig där.

Marken består av $N\times MN\; \backslash times\; M$ rutor, och det går att bygga högst ett hus på en given ruta. Varje ruta har ett värde $a_{x,y}a\_\{x,y\}$ som beskriver hur trevlig den är, på en skala mellan $00$ och $100100$. % $00$ (...) och $100100$ (...).

Excentrikernas mål är att komma så långt bort som möjligt från alla andra, inklusive varandra. Lyckan en excentriker upplever av att bygga sitt hus på ruta $(x,y)(x,y)$ är därmed $a_{x,y}\cdot da\_\{x,y\}\; \backslash cdot\; d$, där $dd$ är det minsta avstånd till någon annan person. Av vana använder sig excentrikerna av manhattanavstånd för att mäta detta; $dd$ definieras alltså som $\min \mathrm{\mid }x-x_2\mathrm{\mid }+\mathrm{\mid }y-y_2\mathrm{\mid }\backslash min\; |x\; -\; x\_2|\; +\; |y\; -\; y\_2|$ över alla andra personers rutor $(x_2,y_2)(x\_2,\; y\_2)$.

Excentrikerna vill nu ha din hjälp med att placera sina hus optimalt, så att summan av lyckan de upplever är så hög som möjligt. Kan du hjälpa dem?

입력

Indatan består av $1010$ testfall, som beskrivs längre ner.

Den första raden innehåller talet $TT$ ($0\le T\le 100\; \backslash le\; T\; \backslash le\; 10$), som beskriver numret på testfallet ($00$ för sample). Den andra raden innehåller talen $NN$, $MM$ och $KK$ ($1\le N,M\le 10001\; \backslash le\; N,\; M\; \backslash le\; 1\backslash ,000$, $2\le K\le N\cdot M2\; \backslash le\; K\; \backslash le\; N\; \backslash cdot\; M$) -- höjden och bredden på markrutnätet, och antalet personer. De följande $NN$ raderna innehåller $MM$ heltal vardera -- värdena $a_{x,y}a\_\{x,y\}$ ($0\le a_{x,y}\le 1000\; \backslash le\; a\_\{x,y\}\; \backslash le\; 100$).

출력

Skriv ut $KK$ rader med husens positioner. Varje rad ska innehålla två tal: först raden för huset (mellan $11$ och $NN$), därefter kolumnen (mellan $11$ och $MM$). Två hus får inte placeras på samma position.

힌트

I exempelfallet vill vi placera ut två hus på ett $2\times 32\; \backslash times\; 3$ rutnät. Exempellösningen placerar ett av husen i det nedre vänstra hörnet och ett i det övre högra hörnet. Båda husens kortaste avstånd till något annat hus kommer då bli $2+1=32\; +\; 1\; =\; 3$, och summan av lycka därmed $3\cdot 30+3\cdot 50=2403\; \backslash cdot\; 30\; +\; 3\; \backslash cdot\; 50\; =\; 240$.

Om det testfallet hade varit ett riktigt testfall och en annan deltagare placerat sina hus i det övre vänstra och nedre högra hörnet (vilket hade uppnått den högre lyckan $270270$) så hade testfallet getts $10\cdot (240\mathrm{/}270{)}^2\approx 7.9010\; \backslash cdot\; (240\; /\; 270)^2\; \backslash approx\; 7.90$ poäng.