This is an approximate problem. There is no exact solution. You must find the most optimal solution. Please, take a look on sample explanation to ensure that you understand the problem correctly.

You are given an integer matrix $A$ of size $N \times M$. You start on the left upper corner cell (with coordinates $(1, 1)$). You can walk in four directions. You can not visit the same cell twice. You have to visit every cell of matrix $A$. When you stand on a cell, your maximum value is updated with the value of element on this cell. Initially, the maximum value is equal to $A_{1, 1}$. Your task is to find the path with the minimum number of changes in the maximum value.

Input format

• First line: Two space-separated integers $N$ and $M$ $(1 \leq N, M \leq 500)$
• Each of the next $N$ lines: $M$ space-separated integers $A_{i, j}$ $(1 \leq A_{i, j} \leq 10^9)$

Output format

In each of the $N \cdot M$ lines, print two numbers that represent the coordinates of the cell of the path. The first one must contain two integers $1$ and $1$.

Verdict and scoring

Your score is equal to the sum of the values of all test cases. 

The value of each test is equal to the number of changes in maximum value.

If at least one of the rules will be violated, then your value for this test will be $0$.

Test generation plan

In 16,6% tests: $(1 \leq N \leq 5, \, 1 \leq M \leq 500)$; elements of matrix $A$ are generated randomly.

In 50% tests: $(1 \leq N, M \leq 500)$; elements of matrix $A$ are generated randomly.

In 33% tests: $(1 \leq N, M \leq 500)$; there is an integer $K$ is equal to the minimum from three values: $50$, $N$ and $M$; elements of matrix $A$ are generated randomly, but $K \cdot K$ largest elements from matrix $A$ are located in the right lower square of matrix $A$ of size $K \times K$.