Yuanyuan has grown tired of the traditional "Tetris" game and has invented a new way to play: the game takes place on an infinitely high board with $N$ columns, numbered $1, 2, \dots, N$ from left to right. In the game, players can use 19 types of base blocks as shown in Figure 1. Each base block is composed of four small squares connected together. The base block shapes are labeled with an ID $T$ ($1 \le T \le 19$):

Figure 1: The 19 shapes of Tetris blocks

Board Description and Game Rules

1. Description of the board state: All possible board states in the game are described by the number of connected small squares in each column. For example, in the board state shown in Figure 2, the board has 4 columns ($N=4$). Column 1 has 3 small squares; column 2 has 2 small squares; column 3 has 3 small squares; column 4 has 0 small squares. Therefore, this board state can be described as $(3, 2, 3, 0)$.
2. Game moves: First, select a base block $T$ ($1 \le T \le 19$), then place it into the target column $C$ ($1 \le C \le N$). This is called a command $(T, C)$, which means the leftmost small square of the base block with shape ID $T$ is aligned with column $C$ and dropped. For example, for the board state in Figure 2, if we select the base block $T=1$ and place it in column 4, i.e., command $(1, 4)$, the block falls to the bottom. The board state immediately after executing command $(1, 4)$ becomes $(3, 2, 3, 4)$. Since the bottom two rows are full, the game rules automatically clear the two full rows, resulting in the board state shown in Figure 3, which can be described as $(1, 0, 1, 2)$.
3. Game end: The game ends when the number of small squares in every column on the board is 0. For example, starting from the board state in Figure 3, selecting base block 9 and placing its leftmost small square in column 1, i.e., command $(9, 1)$, causes it to fall to the bottom. The board state becomes $(2, 2, 2, 2)$. Two rows are filled and automatically cleared, resulting in $(0, 0, 0, 0)$, and the game ends successfully.
4. Boundaries: The game rules state that when placing any base block, it is not allowed to exceed the board boundaries. For example, in Figure 2, where $N=4$, the command $(18, 4)$ would be out of bounds.
5. Floating blocks: The game also prohibits the appearance of "floating" small squares. "Floating" means that in the same column, the small squares are not connected together. For example, Figure 5 illustrates this situation. Given the board state in Figure 2, the commands $(2, 1)$, $(17, 2)$, and $(10, 3)$ are illegal.

Figure 2, Figure 3, Figure 4, Figure 5

Although choosing shapes arbitrarily makes the game much easier, clearing all the blocks is still a headache. Are you willing to try? Now, the "New Tetris" game program is provided to you. This program can read your $(T, C)$ commands and tell you the board state after the commands are completed.

Input

The input files tetris1.in through tetris10.in are already placed in the user directory. The first line of each file contains an integer $N$, the number of columns on the board. The second line contains $N$ integers, representing the number of connected small squares in each column.

Output

This is an answer-submission problem. You should provide ten output files tetris1.out through tetris10.out in the user directory. Each file contains several lines, where each line consists of two integers $T$ and $C$, representing the sequence of commands. The input data is guaranteed to have a solution. If the solution is not unique, you may output any valid set of commands.

Examples

Input 1

4
3 2 3 0

Output 1

1 4
9 1

Subtasks

For each test case, if your output is incorrect or the number of commands exceeds 1,000,000, you get 0 points. If your output is correct and the number of commands does not exceed 100,000, you get 10 points. If your output is correct but the number of commands exceeds 100,000, you will only get 7 points.

Implementation Details

The game program game is located in the user directory. Usage: game <test case number X>. The program will automatically read the input file tetrisX.in and your output file tetrisX.out, where $X=1, 2, \dots, 10$.

• If game exits abnormally, your output is considered incorrect.
• If your output file is invalid, game will point out the first incorrect line.
• If the output is valid, game will generate a tetris.log file. The first line of this file contains the number of columns $N$, and the second line contains $N$ integers, representing the number of connected small squares in each column after playing the game according to your output.

The game program will also display your score on the screen.