50042. Highest Mountain

I'm a slow walker, but I never walk backwards.

Task Description

Given a matrix of mountains, write a program to find the positions of the highest and the second highest mountains for every row, and the position of the overall highest mountain.

There is a matrix of mountains of $n$ rows and $m$ columns. Let $M_{ij}$ denote the mountain in the $i$-th row and $j$-th column. Also let $h_{ij}$ be the height of mountain $M_{ij}$. The row index goes from $1$ to $n$, and the column index goes from $1$ to $m$.

We want to report the column index of the highest and the second highest mountains in a row. If there are multiple highest mountains in the same row, we report the one with the largest column index as the highest mountain, and the one with the second largest column index as the second highest mountain. If there are multiple second highest mountains, we report the one with the largest column index.

We also want to report the row and column index of the overall highest mountain. If there are multiple highest mountains, then report the one with the largest row index. If there are still multiple highest mountains in that row, report the one with the largest column index.

A $3$ by $4$ example here.

$$\begin{bmatrix} 2 & 1 & 3 & 4 \\ 0 & 0 & 1 & 0 \\ 0 & 3 & 2 & 3 \end{bmatrix}$$

For the $i$-th row we define $pc_i$ as the column index of the highest mountain and $qc_i$ as the column index of the second highest mountain. For all rows we define $(ax, ay)$ as the (row index, column index) of the highest mountain.

For example, the first row is $\lbrack 2, 1, 3, 4]$, the second row is $\lbrack 0, 0, 1, 0]$ and the third row is $\lbrack 0, 3, 2, 3]$. In the first row, the highest mountain locate fourth column and the second highest mountain locate third column, so we get $(pc_1, qc_1) = (4, 3)$. Similarly, according to the above mentioned definition, we get $(pc_2, qc_2) = (3, 4)$ and $(pc_3, qc_3) = (4, 2)$. In all rows, the highest mountain locate the first row and the fourth column, as a result, we get $(ax, ay) = (1, 4)$.

Now given the heights of all mountains, report all positions described above.

Input Format

There is one test case.

The first line of the input file contains two integer $n$, $m$, representing the number of rows and columns. Each of the next $n$ lines contains $m$ integers, representing a matrix of the mountains, where the $j$-th integer on line $i$ denotes the height $h_{ij}$ of the mountain $M_{ij}$.

Technical limitation

  • $1 \le n \le 2000000,\; 2 \le m \le 2000000, \; 1 \le n m \le 2000000$
  • $0 \le h_{ij} \; \le 2^{31}-1$

Subtask

  • 30 pt. $1 \le n \le 5,\; 2 \le m \le 5$.
  • 30 pt. $1 \le n \le 1000,\; 2 \le m \le 1000$, $n m \le 100000$.
  • 40 pt. $n m \le 2000000$.

Output Format

For each test case, the output contains $n+1$ lines. Each of the next $n$ lines of output consist of two integers $pc, qc$ separated by a single space, depending on the column index of the highest and second highest of mountain in the $i$-th row. The last line of output consists two integers $ax, ay$ by separated by a single space, depending on the row and column index of the highest of mountain in all rows.

Sample Input 1

3 4
2 1 3 4
0 0 1 0
0 3 2 3

Sample Output 1

4 3
3 4
4 2
1 4

Sample Input 2

4 3
2 1 1
4 3 1
4 0 1
1 2 2

Sample Output 2

1 3
1 2
1 3
3 2
3 1

Discussion