Problem A
Flood

I spelet Flood har du ett rutnät där alla rutor är färglagda i ett antal färger. Målet med spelet är att färglägga alla rutor med samma färg genom ett antal operationer.

Vid varje tidpunkt kan vi dela in rutnätet i dess likfärgade komponenter. En likfärgad komponent är en maximal grupp av rutor med samma färg som alla kan nås från varandra genom att endast röra sig upp, ned, vänster och höger inom komponenten. Notera att varje ruta är del av exakt en likfärgad komponent. En operation består av att färga om alla rutor i en viss likfärgad komponent till en annan färg.

Spelet har precis fått en renässans bland ungdomar, så du vill snabbt koda ihop en klon av spelet. Skriv ett program som, givet ett rutnät och vilka färger alla rutor har, simulerar ett antal operationer och sedan skriver ut vilka färger rutorna har efteråt.

Indata

Den första raden innehåller två heltal $R$ och $C$ ($1 \le R \cdot C \le 200\, 000$), antalet rutor och kolumner i rutnätet.

Detta följs av $R$ rader med $C$ heltal på varje. Dessa beskriver färgerna på alla rutor i rutnätet. Alla färger är mellan $0$ och $99\, 999$, inklusive.

Nästa rad innehåller antalet operationer $Q$ ($1 \le Q \le 100\, 000$). Detta följs av $Q$ rader som beskriver operationerna i den ordning de utförs. En operation består av tre heltal $r$, $c$, $x$ ($1 \le r \le R$, $1 \le c \le C$, $0 \le x \le 99\, 999$) och innebär att du ska färga den komponent som rutan på rad $r$ och kolumn $c$ tillhör med färgen $x$.

Utdata

Skriv ut $R$ rader med $C$ heltal i varje: färgerna på alla rutor efter att samtliga operationer utförts.

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.

12 11
1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 1 1
1 1 1 0 0 0 0 0 1 1 1
1 1 0 0 0 0 0 0 0 1 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 2 2 2 0 0 0 1
1 0 0 0 0 0 0 0 0 0 1
1 1 0 0 0 2 0 0 0 1 1
0 1 1 0 0 2 0 0 1 1 0
0 0 1 1 0 0 0 1 1 0 0
0 0 0 1 1 1 1 1 0 0 0
2
5 5 3
6 2 4

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

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

1 1 1 3
1 1 2 2
1 1 1 2
3 3 1 3

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

1 3 1 2 2 2
3 1 3 1 3 1
3 3 3 3 3 3
3 3 1 3 3 3
3 3 3 3 3 3
3 3 3 3 3 1