The Tower of Hanoi consists of ~N~ disks arranged in three piles numbered ~1~, ~2~, and ~3~. The disks all have distinct sizes, with disk ~1~ being the smallest and disk ~N~ being the largest. Larger disks cannot be placed on top of smaller disks. An arrangement of the disks can thus be represented uniquely by a sequence of ~N~ digits, each being ~1~, ~2~, or ~3~, such that the ~i^\text{th}~ digit represents the pile where disk ~i~ is located.

A legal move consists of taking a single disk from the top of one pile, and placing it at the top of a different pile, such that the result is a valid arrangement. That is, a larger disk cannot be placed on top of a smaller disk. A move can be represented by two integers ~a~ and ~b~, where the corresponding move takes the disk at the top of pile ~a~ and places it at the top of pile ~b~.

Initially, all disks are in pile ~1~. You are given ~Q~ distinct arrangements, and must find a sequence of legal moves that visits all ~Q~ arrangements, in any order. It is permitted to visit an arrangement more than once. The sequence does not need to be optimal. However, it can have at most ~C~ moves.

Constraints

~C = 2\,000\,000~

~1 \le N \le 15~

~1 \le Q \le 20\,000~

The ~Q~ arrangements are distinct.

Subtask 1 [20%]

~N \le 13~

Subtask 2 [20%]

~Q \le 50~

Subtask 3 [50%]

~Q \le 7\,000~

Subtask 4 [10%]

No additional restrictions.

Input Specification

The first line contains two space-separated integers ~N~ and ~Q~.

The next ~Q~ lines each contain a string of ~N~ digits, representing the arrangements to be visited.

Output Specification

The first line of output should contain an integer ~K~, the number of moves. Recall that ~K~ may be at most ~C~.

The next ~K~ lines should each contain two integers ~a~ and ~b~, representing a legal move.

Sample Input

3 2
131
132

Sample Output

6
1 2
1 3
2 1
1 3
1 2
3 1