Problem Description

Ana works in a warehouse that has three piles of boxes, labelled $1$, $2$ and $3$. Each box has a number from $1$ to $n$ written on it, and every number appears on exactly one box.

At the beginning, all the boxes are stacked on top of each other on pile $1$, in some order, while piles $2$ and $3$ are empty.

The boxes are heavy, so Ana moves them one at a time. In one move, she may take the box from the top of one pile and put it on top of a different pile. She must not touch a box that is not on top of its pile, or the pile would fall over.

Ana wants all the boxes to end up on pile $1$, stacked in increasing order from bottom to top: the box with number $1$ at the bottom, the box with number $2$ on top of it, and so on, up to the box with number $n$ at the top. Piles $2$ and $3$ must be empty at the end.

Ana is short on time, so she may make at most $M$ moves. Help her find a sequence of moves that achieves this arrangement. The number of moves does not have to be the smallest possible, but it must not be greater than $M$.

Input Format

The first line contains positive integers $n$ and $M$ ($1 \le n \le 500$, $1000 \le M \le 260\,000$), the number of boxes and the maximum allowed number of moves.

The second line contains $n$ distinct positive integers $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le n$), the numbers written on the boxes on pile $1$, listed from bottom to top. In other words, $p_1$ is the number on the lowest box, and $p_n$ is the number on the box at the top of the pile.

Output Format

In the first line, output an integer $K$ ($0 \le K \le M$), the number of moves Ana should make.

In the $i$-th of the following $K$ lines, output two different numbers $a_i$ and $b_i$ ($a_i,b_i \in \{1,2,3\}$) describing the $i$-th move: Ana takes the box from the top of pile $a_i$ and puts it on top of pile $b_i$. Pile $a_i$ must not be empty when the move is made.

After all $K$ moves, the boxes on pile $1$ must be in the order $1,2,\ldots,n$ from bottom to top, and piles $2$ and $3$ must be empty. If the boxes are already stacked this way at the beginning, you may output $K=0$.

If there are multiple solutions, output any of them.

2 1000
2 1

4
1 2
1 3
2 1
3 1

3 1000
3 1 2

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

4 1000
1 2 3 4

0

Hint

Clarification of the first example

The box with number $1$ is on top, above the box with number $2$. Ana first moves box $1$ to pile $2$, and then box $2$ to pile $3$. After that, she puts box $1$ back on pile $1$, and then box $2$ on top of it, so that box $1$ is at the bottom and box $2$ is at the top.

Clarification of the second example

We write the contents of each pile as a sequence of numbers from bottom to top. At the beginning, pile $1$ contains $[3,1,2]$, so the box with number $2$ is on top, and piles $2$ and $3$ are empty. The table shows the state of all piles after each move:

After the seventh move, pile $1$ contains boxes $1,2,3$ from bottom to top, and piles $2$ and $3$ are empty, so the arrangement is correct. This is not the only correct sequence of moves, nor is it the shortest one.

Clarification of the third example

The boxes on pile $1$ are already in the order $1,2,3,4$ from bottom to top, and piles $2$ and $3$ are empty. This is exactly the arrangement Ana wants, so she does not need to make any moves, and $K=0$ is a correct answer.

Scoring