Spirale

Στον μικρό Stjepan αρέσει συχνά να βγαίνει με τους φίλους του και να διασκεδάζει σε ένα δημοφιλές νυχτερινό κέντρο στο Ζάγκρεμπ. Ωστόσο, ο Stjepan πίνει μερικές φορές πάρα πολύ αναψυκτικό και ζαλίζεται από όλη τη ζάχαρη. Η χθεσινή βραδιά ήταν ένα παράδειγμα αυτού, γι' αυτό ο Στιέπαν είχε την ίδια εικόνα στο μυαλό του όλη την ώρα. Ήταν ένα σκαρίφημα από σπείρες αριθμού κάποιου είδους. Δεδομένου ότι δεν μπορεί να θυμηθεί καλά πώς ήταν η εικόνα, αλλά μπορεί να την περιγράψει, σας ζητά να του την ανασκευάσετε.

Ο Stjepan θυμάται ότι η εικόνα είχε το σχήμα ενός πίνακα που αποτελείται από αριθμούς γραμμένους σε N σειρές και M στήλες. Επίσης, θυμάται ότι υπήρχαν K σπείρες σε αυτόν τον πίνακα. Για κάθε σπείρα, είναι γνωστή η αρχική θέση, καθώς και η κατεύθυνση προς την οποία κινείται, η οποία μπορεί να είναι δεξιόστροφα και αριστερόστροφα. Για κάθε σπείρα, είναι γνωστή η αρχική θέση, καθώς και η κατεύθυνση προς την οποία κινείται, η οποία μπορεί να είναι δεξιόστροφα και αριστερόστροφα. Ένα παράδειγμα φαίνεται στις παρακάτω εικόνες. Οι σπείρες δημιούργησαν την εικόνα του Stjepan σε ακριβώς ~10^{100}~ βήματα με τον ακόλουθο τρόπο:

1. Αρχικά, το τραπέζι είναι άδειο και κάθε σπείρα βρίσκεται στη δική του αρχική θέση. 2.
2. Σε κάθε επόμενο βήμα, κάθε σπείρα μετακινείται στην επόμενη θέση της. Είναι πιθανό, κατά καιρούς, οι σπείρες να φεύγουν από τα όρια του πίνακα, αλλά και να επιστρέφουν εντός αυτού.
3. Μετά από ακριβώς ~10^{100}~ βήματα, για κάθε πεδίο στον πίνακα, η τελική τιμή είναι η τιμή του πρώτου βήματος στο οποίο μία από τις σπείρες άγγιξε αυτό το πεδίο.

Εικόνα 1: μια σπείρα που κινείται αριστερόστροφα

Εικόνα 2: μια σπείρα που κινείται δεξιόστροφα.

Είσοδος

Η πρώτη γραμμή εισαγωγής περιέχει θετικούς ακέραιους αριθμούς ​\(N , Μ (1 \le N, M \le 50)\) και \( Κ (1 \le K ​\le ​N​*M​)\). Καθεμία από τις \(Κ\) ακόλουθες γραμμές περιέχει τρεις θετικούς ακέραιους \(X,​Y_i\) και ​~T_i (1 \le X \le N, 1 \le Y \le M, 0 \le T \le 1)~ , την αρχική θέση της i-οστής σπείρας και την κατεύθυνσή της (0 - δεξιόστροφα, 1 - αριστερόστροφα). Δεν θα ξεκινήσουν δύο σπείρες στο ίδιο πεδίο.

Έξοδος

Πρέπει να εξάγετε ​N γραμμές με M αριθμούς, που αντιπροσωπεύουν τον πίνακα αφού κάθε σπείρα κάνει ~10^{100}~ βήματα.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας 50% των συνολικών πόντων, θα ισχύει: \(​N​=​MiK​=1\) και \(X_i=​Y_i​=\lfloor \frac{N+1}{2} \rfloor\), δηλαδή ​~X_i~​ και ​~Y_i~ θα είναι ίσοι με την ακέραια διαίρεση του Ν+1 με το 2.

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

input

3 3 1
2 2 0

output

9 2 3
8 1 4
7 6 5

input

3 3 1
2 2 1

output

3 2 9
4 1 8
5 6 7

input

3 3 2
1 1 0
1 2 0

output

1 1 4
6 5 5
19 18 17

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

Για λόγους απλότητας, το γράμμα Α προστέθηκε στους αριθμούς από την πρώτη σπείρα και το γράμμα Β στους αριθμούς από τη δεύτερη σπείρα. Εμφανίζονται μόνο τα πρώτα 20 βήματα της πρώτης σπείρας και 21 βήματα της δεύτερης σπείρας. Τα πεδία με γκρι χρώμα είναι τα πεδία από τον πίνακα που μας ενδιαφέρουν, όλα τα άλλα πεδία είναι εκτός των ορίων του πίνακα, αλλά εμφανίζονται για να απεικονίσουν τον τρόπο με τον οποίο οι σπείρες κινούνται έξω από τον πίνακα.