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

Problem statement

You are given an integer matrix $A$ of size $N \times N$. You can start at any cell of the matrix. You can walk in four directions (left, right, up, and down). You can not visit the same cell twice. Here, $B_1, B_2, \ldots, B_k$ denote the values of cells of the path in order of bypass. The value of the path is equal to $\sum_{i=1}^{k} B_i \cdot i$. Your task is to find the path with maximum value.

Input format

• First line contains two space-separated integers $N$ $(1 \leq N \leq 1000)$
• Each of the next $N$ lines contains $N$ space-separated integers $A_{i, j}$ $(1 \leq A_{i, j} \leq 10^9)$

Output format

$X$ $(1 \leq X \leq N \cdot N)$ is the length of path that you found. The format of the output is as follows:

• In the first line, print $X$ denoting the length of path.
• In each of the $X$ lines, print two numbers denoting the coordinates of cell of the path.

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 value of path that you found.

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

Test generation plan

• In 10% tests: $(1 \leq N \leq 6)$ denoting the elements of matrix $A$ are generated randomly.
• In 30% tests: $(1 \leq N \leq 1000)$ denoting the elements of matrix $A$ are a random permutation of size $N \cdot N$ (elements from $1$ to $N \cdot N$).
• In 60% tests: $(1 \leq N \leq 1000)$ denoting the elements of matrix $A$ are generated randomly.