Skakac

Ο Mirko και ο Slavko παίζουν το δημοφιλές νέο παιχνίδι γνωστό ως The Knight. Ο Mirko τοποθετεί ένα κομμάτι σκακιού ιππότη σε μια σκακιέρα ~N \times N~ και, με τον Σλάβκο δεμένα τα μάτια, κάνει ακριβώς ~T~ κινήσεις, μία ανά δευτερόλεπτο. Μετά από αυτό, ο Slavko πρέπει να μαντέψει την τελική θέση του ιππότη για να κερδίσει.
Η σκακιέρα σε αυτό το παιχνίδι είναι ασυνήθιστη καθώς κάθε τετράγωνο είναι μπλοκαρισμένο για κάπιο μέρος του χρόνου. Πιο συγκεκριμένα, κάθε τετράγωνο χαρακτηρίζεται από έναν θετικό ακέραιο. Ένα τετράγωνο που επισημαίνεται με τον αριθμό ~K~ είναι καθαρό μόνο κατά τη διάρκεια των δευτερολέπτων ~0,\;K,\;2K,\;3K~ κ.λπ..Είναι μπλοκαρισμένο όλες τις άλλες φορές. Ο ιππότης μπορεί, φυσικά, να καταλάβει ένα τετράγωνο μόνο όταν το τετράγωνο είναι καθαρό.
Το παιχνίδι αρχίζει το δευτερόλεπτο 0. Σε κάθε δευτερόλεπτο ο Mirko πρέπει να κάνει μια κίνηση (επιλέγοντας μία από τις 8 πιθανές κινήσεις σχήματος ~L~, δύο τετράγωνα προς τη μία κατεύθυνση και ένα τετράγωνο στην άλλη, σύμφωνα με τους τυπικούς κανόνες σκακιού), με την προϋπόθεση ότι το τετράγωνο προορισμού δεν μπλοκάρεται κατά το επόμενο δευτερόλεπτο. Βοηθήστε τον Slavko γράφοντας ένα πρόγραμμα για να υπολογίσει όλα τα πιθανά τετράγωνα που μπορεί να καταλάβει ο ιππότης μετά από ~T~ κινήσεις.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο θετικούς ακέραιους, ~N\;(3 \leq N \leq 30)~, το μέγεθος της σκακιέρας και ~T\;(1 \leq T \leq 1\,000\,000)~, τον αριθμό των κινήσεων που θα κάνει ο Mirko.
Η δεύτερη γραμμή εισόδου περιέχει δύο θετικούς ακέραιους ~X~ και ~Y\;(1 \leq X,\;Y \leq N)~, τους δείκτες σειρών και στηλών του αρχικού τετραγώνου του ιππότη που επιλέχτηκε από τον Mirko. Οι επόμενες ~N~ γραμμές περιέχουν η καθεμία ~N~ θετικούς ακέραιους αριθμούς μικρότερους από ~10^9~ (ένα δισεκατομμύριο), τις τιμές του ~K~ για τα αντίστοιχα τετράγωνα της σκακιέρας.

Έξοδος

Η πρώτη γραμμή εξόδου πρέπει να περιέχει τον μη αρνητικό ακέραιο ~M~, τον αριθμό των τετραγώνων που μπορεί να καταλάβει ο ιππότης μετά από ~T~ κινήσεις.
Οι επόμενες ~M~ γραμμές πρέπει να περιέχουν δείκτες αυτών των τετραγώνων, ταξινομημένους κατά αύξηση του δείκτη σειρών, με κελιά στην ίδια σειρά ταξινομημένα κατά αυξανόμενο δείκτη στήλης.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~40~% των συνολικών πόντων, ο αριθμός των κινήσεων ~T~ θα είναι μικρότερος από ~50\,000~.

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

input

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

output

2
1 1
1 3

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

Η κατάσταση της σκακιέρας σε κάθε δευτερόλεπτο φαίνεται παρακάτω. Τα καθαρά κελιά συμβολίζονται με ".", τα αποκλεισμένα κελιά με "#" και οι πιθανές τοποθεσίες του ιππότη με "K".

input

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

output

5
1 4
2 1
2 5
4 5
5 2

input

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

output

0