XOR Sort

Δίνεται ακέραιος ~S~ και πίνακας ~A~ αποτελούμενος από ~N~ μη-αρνητικους ακεραίους, με αρίθμηση από το ~1~. Επιτρέπεται να κάνετε την ακόλουθη πράξη στον πίνακα:

• Διάλεξε οποιαδήποτε θέση του πίνακα ~i:\ 1 \leq i \leq N~
• Διάλεξε μία διπλανή θέση του πίνακα ~j:\ j = i \pm 1,\ 1 \leq j \leq N~
• Αντικατάστησε το ~A_i~ με την δυαδική πράξη XOR μεταξύ των ~A_i, A_j~: $$\displaystyle A_i \gets A_i \oplus A_j$$

Στόχος είναι να μετατρέψετε τον ~A~ σε ταξινομημένο πίνακα:

• Αν ~S = 1~, τότε πρέπει να είναι γνησίως αύξων: ~A_i < A_{i+1},\ 1 \leq i \leq N~
• Αν ~S = 2~, τότε πρέπει να είναι μη-φθίνων: ~A_i \leq A_{i+1},\ 1 \leq i \leq N~

Να βρείτε ακολουθία πράξεων που επιτυγχάνουν τον στόχο. Δεν χρειάζεται να βρείτε την μικρότερη ακολουθία, αρκεί να μην ξεπεράσουν τις ~40,000~.

Μορφή Εισόδου

Η πρώτη γραμμή περιέχει 2 ακεραίους ~N, S~. Η επόμενη γραμμή περιέχει ~N~ ακεραίους ~A_1, A_2, \dots , A_N~.

Μορφή Εξόδου

Η πρώτη γραμμή περιέχει μοναδικό ακέραιο ~0 \leq K \leq 40,000~: το πλήθος των πράξεων. Ακολουθούν ~K~ γραμμές που περιγράφουν τις πράξεις σε χρονολογική σειρά: κάθε γραμμή περιέχει τους 2 ακεραίους ~i, j~, όπως ορίζονται παραπάνω.

Περιορισμοί - Υποπροβλήματα

• ~1 \leq S \leq 2~
• ~2 \leq N \leq 1,000~
• ~0 \leq A_i < 2^{20}~

Βαθμολογία	Περιορισμοί
~25~	~2 \leq N \leq 150,\ S = 1,~ όλα τα ~A_i~ είναι διακριτά
~35~	~2 \leq N \leq 200,\ S = 1,~ όλα τα ~A_i~ είναι διακριτά
~40~	~2 \leq N \leq 1,000,\ S = 2~

Παράδειγμα 1

Είσοδος:

5 1
3 2 8 4 1

Έξοδος:

3
1 2
4 3
5 4

Εξήγηση:

   [3, 2, 8,  4, 1] => [1, 2, 8,  4,  1] =>
=> [1, 2, 8, 12, 1] => [1, 2, 8, 12, 13]

Παράδειγμα 2

Είσοδος:

5 2
4 4 2 0 1

Έξοδος:

3
3 2
4 3
5 4

Εξήγηση:

   [4, 4, 2, 0, 1] => [4, 4, 6, 0, 1] =>
=> [4, 4, 6, 6, 1] => [4, 4, 6, 6, 7]