Problem G
Gosedjursmani

Olivia och Anton är på Liseberg, och de har hittat en kloautomat med $N$ stycken gosedjur, numrerade från $1$ till $N$. Olivia är väldigt skicklig, och vill visa upp sina färdigheter för Anton. Den tvådimensionella kloautomaten kan modelleras som ett rutnät av storlek $R \times C$, med $R$ rader och $C$ kolumner. I den ligger gosedjuren tätt packade, och varje ruta hör till ett gosedjur. Ett gosedjur kan bestå av flera rutor i rutnätet, och varje gosedjur bildar en sammanhängande figur. Med andra ord kan du rita varje gosedjur med en tjock penna utan att lyfta pennan från pappret. Alla $R \times C$ rutor täcks av ett gosedjur, det finns alltså inga tomma rutor. I ett spel kan Olivia välja ett gosedjur som inte har något annat gosedjur direkt ovanför sig, och lyfta upp det ur kloautomaten. Eftersom Olivia inte ännu frågat Anton om vilket hans favoritdjur är, vill hon för varje gosedjur veta hur många spel hon sammanlagt behöver göra innan hon kan lyfta upp det djuret.

Indata

På den första raden står talen $N$, $R$ och $C$ ($1 \leq N \leq R \times C \leq 4 \times 10^{5}$). Därefter följer $R$ rader, som beskriver rutnätet. Den första raden beskriver toppen av kloautomaten, och den sista beskriver botten. På den $i$:te raden står $C$ heltal $a_{i,1}, a_{i,2}, ..., a_{i,C}$ ($1 <= a_{i,j} <= N$). Gosedjur nummer $x$ består av alla rutor $i,j$ som uppfyller $a_{i,j} = x$. Det är garanterat att varje gosedjur består av minst en ruta, och att varje gosedjur bildar en sammanhängande region.

Utdata

För varje gosedjur $1, 2, ..., N$, skriv ut antalet spel Olivia behöver göra innan hon kan lyfta ut djuret. Om det inte går, skriv ut $-1$.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1

I exempelfall 1 ser kloautomaten ut som i figuren.

För att lyfta upp gosedjur $1$ behöver vi inte lyfta upp något annat, alltså är svaret $0$. För att lyfta upp gosedjur $2$ behöver vi först lyfta upp $3$, $4$, $6$ och $7$, alltså är svaret $4$. För att lyfta upp gosedjur $3$ behöver vi inte lyfta upp någon annan innan. För att lyfta upp gosedjur $4$ behöver vi först lyfta upp $3$ och $6$, alltså är svaret $2$. För gosedjur $5$, $6$, $7$ är svaren $3$, $0$, $3$ respektive.

Såhär ser det ut när man lyfter gosedjur nummer $3$.

Förklaring av exempelfall 4

Varken gosedjur $1$ eller $2$ har någonting ovanför sig, så svaret för bägge är $0$. För att lyfta upp gosedjur $3$ behöver man först lyfta upp gosedjur $4$. För att lyfta upp gosedjur $4$ behöver man först lyfta upp gosedjur $3$. För att lyfta upp gosedjur $3$ behöver man först lyfta upp gosedjur $4$. För att lyfta upp gosedjur $4$ behöver man först lyfta upp gosedjur $3$. För att lyfta upp gosedjur $3$ behöver man först lyfta upp gosedjur $4$. Svaret för båda är $-1$, eftersom vi aldrig kan lyfta upp någon av dem.

7 4 4
1 3 3 6
1 4 4 4
1 7 4 5
1 2 4 5

0 4 0 2 3 0 3 

4 5 1
2
1
1
3
4

1 0 2 3 

5 4 5
1 1 2 2 3
1 1 2 2 3
4 2 2 2 3
4 2 5 2 3

0 1 0 1 2 

4 4 4
1 1 2 2
3 3 3 2
3 4 3 2
3 3 3 2

0 0 -1 -1