Tri

Η Ana εργάζεται σε μια αποθήκη που διαθέτει τρεις στοίβες από κουτιά, με ετικέτες ~1~, ~2~ και ~3~. Κάθε κουτί έχει γραμμένο πάνω του έναν αριθμό από το 1 έως το ~n~, και κάθε αριθμός εμφανίζεται σε ακριβώς ένα κουτί.

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

Τα κουτιά είναι βαριά, οπότε η Ana μετακινεί ένα κάθε φορά. Σε μία κίνηση, μπορεί να πάρει το κουτί που βρίσκεται στην κορυφή μιας στοίβας και να το τοποθετήσει στην κορυφή μιας διαφορετικής στοίβας. Δεν πρέπει να αγγίξει κάποιο κουτί που δεν βρίσκεται στην κορυφή μιας στοίβας, γιατί τότε η στοίβα θα καταρρεύσει.

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

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

Είσοδος

Η πρώτη γραμμή θα περιέχει δύο θετικούς ακέραιους ~n~ και ~M~ (~1 \le n \le 500~, ~1000 \le M \le 260.000~), τον αριθμό των κουτιών και τον μέγιστο επιτρεπόμενο αριθμό κινήσεων.

Η δεύτερη γραμμή θα περιέχει ~n~ διαφορετικούς θετικούς ακέραιους ~p_1,\ p_2,\ ...,\ p_n~ (~1 \le p_i \le n~), τους αριθμούς που είναι γραμμένοι στα κουτιά της στοίβας ~1~, με τη σειρά από κάτω προς τα πάνω. Με άλλα λόγια, το ~p_1~ είναι ο αριθμός στο χαμηλότερο κουτί και το ~p_n~ είναι ο αριθμός στο κουτί που βρίσκεται στην κορυφή της στοίβας.

Έξοδος

Στην πρώτη γραμμή, να εκτυπώσετε έναν ακέραιο ~K~ (~0 \le K \le M~), τον αριθμό των κινήσεων που πρέπει να κάνει η Ana.

Στις επόμενες ~K~ γραμμές, να εκτυπώσετε δύο διαφορετικούς αριθμούς ~a_i~ και ~b_i~ (~a_i, b_i \in~ {~1~, ~2~, ~3~}), οι οποίοι περιγράφουν την ~i~-οστή κίνηση: η Ana παίρνει το κουτί από την κορυφή της στοίβας ~a_i~ και το τοποθετεί στην κορυφή της στοίβας ~b_i~. Η στοίβα ~a_i~ δεν πρέπει να είναι άδεια τη στιγμή που πραγματοποιείται η κίνηση.

Μετά από όλες τις ~K~ κινήσεις, τα κουτιά στη στοίβα ~1~ πρέπει να βρίσκονται στη σειρά ~1,\ 2,\ ...,\ n~ από κάτω προς τα πάνω, ενώ οι στοίβες ~2~ και ~3~ πρέπει να είναι άδειες.

Αν τα κουτιά είναι ήδη στοιβαγμένα με αυτή τη σειρά στην αρχή, μπορείτε να εκτυπώσετε ~K = 0~.

Αν υπάρχουν πολλές λύσεις, εκτυπώστε οποιαδήποτε από αυτές.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~18~	~n \le 5~, ~M = 1000~
~2~	~31~	~M = 260.000~
~3~	~54~	~M = 12.500~
~4~	~7~	~M = 5000~

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

input

2 1000
2 1

output

4
1 2
1 3
2 1
3 1

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

Το κουτί με τον αριθμό ~1~ βρίσκεται στην κορυφή, πάνω από το κουτί με τον αριθμό ~2~.

Αρχικά, η Ana μετακινεί το κουτί ~1~ στη στοίβα ~2~ και στη συνέχεια το κουτί ~2~ στη στοίβα ~3~. Έπειτα, τοποθετεί ξανά το κουτί ~1~ στη στοίβα ~1~ και, στη συνέχεια, το κουτί ~2~ από πάνω του, έτσι ώστε το κουτί ~1~ να βρίσκεται στο κάτω μέρος και το κουτί ~2~ στην κορυφή.

input

3 1000
3 1 2

output

7
1 2
1 3
1 2
3 1
2 3
2 1
3 1

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

Γράφουμε τα περιεχόμενα κάθε στοίβας ως μια ακολουθία αριθμών από κάτω προς τα πάνω. Στην αρχή, η στοίβα ~1~ περιέχει ~[3,\ 1,\ 2]~, επομένως το κουτί με τον αριθμό ~2~ βρίσκεται στην κορυφή, ενώ οι στοίβες ~2~ και ~3~ είναι άδειες. Ο παρακάτω πίνακας δείχνει την κατάσταση και των τριών μετά από κάθε κίνηση:

Κίνηση	Στοίβα ~1~	Στοίβα ~2~	Στοίβα ~3~
~1~ → ~2~	~[3,\ 1]~	~[2]~	~[ ]~
~1~ → ~3~	~[3]~	~[2]~	~[1]~
\(1 → 2\)	~[ ]~	~[2,\ 3]~	~[1]~
~3~ → ~1~	~[1]~	~[2,\ 3]~	~[ ]~
~2~ → ~3~	~[1]~	~[2]~	~[3]~
~2~ → ~1~	~[1,\ 2]~	~[ ]~	~[3]~
~3~ → ~1~	~[1,\ 2,\ 3]~	~[ ]~	~[ ]~

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

input

4 1000
1 2 3 4

output

0

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

Τα κουτιά στη στοίβα ~1~ βρίσκονται ήδη στη σειρά ~1~, ~2~, ~3~, ~4~ από κάτω προς τα πάνω, ενώ οι στοίβες ~2~ και ~3~ είναι άδειες. Αυτή είναι ακριβώς η διάταξη που θέλει η Ana, επομένως δεν χρειάζεται να κάνει καμία κίνηση και η απάντηση ~K = 0~ είναι σωστή.