Little C is playing a ball-sorting game. He has $n + 1$ pillars in front of him, numbered from $1$ to $n + 1$. Initially, pillars $1, 2, \dots, n$ each have $m$ balls placed on them from bottom to top, and pillar $n + 1$ has no balls. There are $n \times m$ balls in total, with $n$ colors, and there are exactly $m$ balls of each color.

Initially, the balls on a pillar can be of various colors. Little C's task is to move all balls of the same color to the same pillar. This is the only goal, and there is no restriction on which pillar each color of balls ends up on.

Little C can achieve this goal through a series of operations. An operation moves a ball from one pillar to another. Specifically, the requirements for moving a ball from pillar $x$ to pillar $y$ are:

1. Pillar $x$ must have at least one ball;
2. Pillar $y$ must have at most $m - 1$ balls;
3. Only the topmost ball of pillar $x$ can be moved to the top of pillar $y$.

Little C's goal is not hard to achieve, so he decides to add some difficulty for himself: on the basis of completing the goal, the number of operations used must not exceed $820000$. In other words, Little C needs to complete the goal using at most $820000$ operations.

Little C is stumped, but he believes you can do it. Please provide an operation sequence to complete Little C's goal. There may be multiple valid sequences; you only need to output any one of them. The problem guarantees that a valid sequence always exists.

Input Format

The first line contains two space-separated integers $n$ and $m$, representing the number of colors of the balls and the number of balls of each color, respectively.

Each of the next $n$ lines contains $m$ space-separated integers. The integers in the $i$-th line represent the colors of the balls on the $i$-th pillar, ordered from bottom to top.

Output Format

The first line of your output should contain a single integer $k$, representing the number of operations in your sequence. You should ensure that $0 \le k \le 820000$.

Each of the next $k$ lines should contain two space-separated positive integers $x$ and $y$, representing moving the topmost ball of pillar $x$ to the top of pillar $y$. You should ensure that $1 \le x, y \le n + 1$ and $x \neq y$.

Examples

Input 1

2 3
1 1 2
2 1 2

Output 1

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

Note

The content of the pillars is given from bottom to top.

Explanation of Sample 1:

For Sample 2, see ball/ball2.in and ball/ball2.ans in the player's directory.

For Sample 3, see ball/ball3.in and ball/ball3.ans in the player's directory.

Constraints

For all test cases, it is guaranteed that $2 \le n \le 50$, $2 \le m \le 400$.

Checker

To facilitate testing, a checker program checker.cpp is provided in the ball directory. You can compile this program and use it to validate your output file. Please note that it is not completely identical to the checker used for final evaluation, and you do not need to worry about the details of its implementation.

The compilation command is:

g++ checker.cpp -o checker

The usage of the checker is:

checker <input_file> <output_file>

where the arguments represent the input file and your output file, respectively.

If the numbers in your output are out of range or invalid, the checker will provide a corresponding prompt. If the numbers are within the valid range but the sequence of operations is incorrect, the checker will output a brief error message:

1. A x: indicates that the $x$-th operation is invalid.
2. B x: indicates that after all operations are completed, the balls on the $x$-th pillar are invalid.

If your solution is correct, the checker will output OK.