Paint

Θα αναπαραστήσουμε την περιοχή σχεδίασης του ~MS Paint~ ως ένα ορθογώνιο πλέγμα τετραγωνικών μονάδων χωρισμένο σε γραμμές ~R~ και στήλες ~S~. Κάθε τετράγωνο του πλέγματος αντιπροσωπεύει ένα μόνο pixel που μπορεί να χρωματιστεί σε ένα από τα ~10^5~ διαφορετικά χρώματα. Όταν ο χρήστης εφαρμόζει το εργαλείο κουβά γεμίσματος με χρώμα ~A~ σε ένα εικονοστοιχείο(pixel) ~(r,\,s)~ που είναι χρωματισμένο στο χρώμα ~B~, τότε όλα τα εικονοστοιχεία στη μονόχρωμη γειτονιά του εικονοστοιχείου ~(r,\,s)~ αλλάζουν το χρώμα τους σε ~A~. Μονόχρωμη γειτονιά ενός εικονοστοιχείου ~(r,\,s)~ είναι ένα σύνολο εικονοστοιχείων που είναι προσβάσιμα περπατώντας από το ~(r,\,s)~ στις τέσσερις γενικές κατευθύνσεις (πάνω, κάτω, αριστερά και δεξιά) χωρίς αλλαγή του χρώματος του pixel. Σημειώστε ότι το εικονοστοιχείο ~(r,\,s)~ είναι μέρος της μονόχρωμης γειτονιάς του.

Σας δίνεται μια αρχική εικόνα που σχεδιάστηκε στο ~MS Paint~ μαζί με ~Q~ οδηγίες που πρέπει να εκτελεστούν με τη δεδομένη σειρά. Κάθε οδηγία σάς λέει σε ποιο pixel πρέπει να εφαρμόσετε το εργαλείο κουβά γεμίσματος και με ποιο χρώμα. Το καθήκον σας είναι να βρείτε πώς φαίνεται η εικόνα μετά την εκτέλεση όλων των εντολών.

Είσοδος

Η πρώτη γραμμή περιέχει τους ακέραιους αριθμούς ~R~ και ~S~ από την περιγραφή του προβλήματος.
Κάθε μία από τις επόμενες ~R~ γραμμές περιέχει ~S~ μη αρνητικούς ακέραιους αριθμούς μικρότερους από το ~100\,000~ που αντιπροσωπεύουν την αρχική εικόνα σχεδιασμένη στο ~MS Paint~.
Πιο συγκεκριμένα, ο ~j~-στός αριθμός στην ~i~-οστή σειρά της εικόνας αντιπροσωπεύει το χρώμα του pixel ~(i,\,j)~.
Η επόμενη γραμμή περιέχει έναν ακέραιο ~Q~ από την περιγραφή του προβλήματος. Η ~i~-οστή των επόμενων ~Q~ γραμμών περιέχει ακέραιους ~r_i,\,s_i~ και ~c_i~ ~(1 \le r_i \le R,\,1 \le s_i \le S,\,0 \le c_i < 100\,000)~, που αντιπροσωπεύουν την ~i~-οστή εντολή που σας λέει να χρησιμοποιήσετε το εργαλείο κουβά γεμίσματος με χρώμα ~c_i~ στο pixel ~(r_i,\,s_i )~.

Έξοδος

Θα πρέπει να τυπώσετε την τελική κατάσταση της εικόνας στην ίδια μορφή που δόθηκε στην είσοδο.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	8	~1 \le R \cdot S \le 10\,000,\,1 \le Q \le 10\,000~
2	9	~R = 1, 1 \le S \le 200\,000,\,1 \le Q \le 100\,000~
3	31	~1 \le R \cdot S \le 200\,000,\,1 \le Q \le 100\,000~ Κάθε pixel θα χρωματίζεται είτε στο χρώμα ~0~ είτε στο χρώμα ~1~.
4	52	~1 \le R \cdot S \le 200\,000,\,1 \le Q \le 100\,000~

Παραδείγματα

input

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

output

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

Επεξήγηση 1ου παραδείγματος

Το σχήμα από την περιγραφή του προβλήματος αντιστοιχεί στην είσοδο του 1ου παραδείγματος. Το λευκό χρώμα αντιστοιχεί στον αριθμό ~0~, το κόκκινο χρώμα αντιστοιχεί στον αριθμό ~1~, το μπλε χρώμα αντιστοιχεί στον αριθμό ~2~, το πράσινο χρώμα αντιστοιχεί στον αριθμό ~3~ και το κίτρινο στον αριθμό ~4~.

input

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

output

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

input

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

output

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