Rotacije

Η διάσημη αρχαιολόγος Diana Jones ανακάλυψε ένα μυστικό πέρασμα που οδηγεί σε κρυμμένο θησαυρό κοντά στο Nowhere, Κάνσας. Το πέρασμα είναι φραγμένο από μια πέτρινη πύλη που έχει έναν αρχαίο μηχανισμό ξεκλειδώματος λαξευμένο σε αυτό. Ευτυχώς, έχει αναγνωρίσει αμέσως τα λαξευμένα σύμβολα:

1. Ο μηχανισμός ξεκλειδώματος είναι ένας πίνακας με γραμμές ~R~ και στήλες ~C~. Κάθε κελί περιέχει ένα μοναδικό θετικό ακέραιο μεταξύ ~1~ και ~R*C~. Εκ πρώτης όψεως, οι αριθμοί φαίνονται να είναι σε τυχαία σειρά.
2. Ο μηχανισμός περιέχει οδοντωτούς τροχούς που μπορεί να χρησιμοποιήσει η Diana για να αναδιατάξει τα κελιά του πίνακα. Σε μια κίνηση μπορεί να περιστρέψει οποιαδήποτε ομάδα γειτονικών κελιών ~2~ επί ~2~ δεξιόστροφα κατά ~90~ μοίρες.
3. Η πύλη θα ξεκλειδωθεί όταν οι αριθμοί αναδιατάσσονται σε σειρά ταξινόμησης μείζονος σειράς (το επάνω αριστερό κελί πρέπει να περιέχει ~1~, το κελί στα δεξιά του ~2~ και ούτω καθεξής μέχρι το κάτω δεξί κελί, που πρέπει να περιέχει ~R*C~).

Για παράδειγμα, για την αρχική διάταξη που φαίνεται στην πρώτη εικόνα, αρκούν δύο κινήσεις για να ξεκλειδώσει ο μηχανισμός:

Γράψτε ένα πρόγραμμα που, δεδομένης της αρχικής διάταξης των κελιών, βρίσκει μια ακολουθία κινήσεων που ξεκλειδώνει τον μηχανισμό. Ο αριθμός των κινήσεων δεν χρειάζεται να είναι ο βέλτιστος, ωστόσο δεν πρέπει να υπερβαίνει τις ~100\,000~.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τους δύο θετικούς ακέραιους ~R~ και ~C~ ~(2 \le R \le C \le 25)~.
Καθεμία από τις ακόλουθες γραμμές ~R~ περιέχει ~C~ θετικούς ακέραιους αριθμούς ~Z_{ij}~ ~(1 \le Z_{ij} \le R*C)~, οι αριθμοί λαξευμένοι στα αντίστοιχα κελιά του μηχανισμού, που περιγράφει την αρχική διάταξη.

Έξοδος

Η έξοδος πρέπει να περιέχει την απαιτούμενη ακολουθία κινήσεων, μία ανά γραμμή. Για κάθε κίνηση, εκτυπώστε δύο θετικούς ακέραιους ~M~ και ~N~ ~(1 \le M \le R-1,\,1 \le N \le C-1)~ που αντιπροσωπεύουν τον δείκτη γραμμής και στήλης του επάνω αριστερά κελιού στην ομάδα ~2~-επί-~2~ που περιστράφηκε σε αυτήν την κίνηση.
Σημείωση: Για όλα τα δεδομένα εισόδου, μια λύση, όχι απαραίτητα μοναδική, θα υπάρχει πάντα.

Βαθμολογία

Σε αρχεία ελέγχου συνολικής αξίας ~40~ πόντων, το ~R*C~ θα είναι το πολύ ~9~. Σε αρχεία ελέγχου συνολικής αξίας ~40~ πόντων, το ~R~ θα είναι ίσο με ~2~. Σε αρχεία ελέγχου συνολικής αξίας ~60~ πόντων, ισχύει τουλάχιστον ένας από τους δύο παραπάνω περιορισμούς.

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

input

2 3
3 2 6
1 4 5

output

1 1
1 2

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

Σύμφωνα με την εικόνα στην περιγραφή του προβλήματος, η αρχική διάταξη μπορεί να διαταχθεί σε δύο κινήσεις: πρώτα περιστρέφουμε την ομάδα με την επάνω αριστερή γωνία στη σειρά ~1~ και τη στήλη ~1~ και, στη συνέχεια, την ομάδα με την επάνω αριστερή γωνία στη σειρά ~1~ και στη στήλη ~2~.

input

3 3
1 2 3
4 6 9
7 5 8

output

2 2

input

2 4
1 2 7 3
5 6 8 4

output

1 3
1 3
1 3