Saddle point
Time: 1 s · Memory: 256 MB
- Matrices
Statement
A saddle point of a matrix is an element that is the smallest in its row (no element of the row is smaller) and the largest in its column (no element of the column is larger).
You are given an matrix. Find the row and column numbers of the first saddle point in row order (left to right, top to bottom). If there is none — -1.
Input format
The first line contains and (). The next lines contain the matrix ().
Output format
A single line with two numbers — the row and the column (from ), or -1.
Examples
Input
3 3 1 2 3 4 5 6 7 8 9
Output
3 1
Input
2 2 1 2 2 1
Output
-1
Note
Precompute the minimum of every row and the maximum of every column — then each element is checked with two comparisons. In the first example is the minimum of row 3 and the maximum of column 1 — the answer is 3 1. The second example has no saddle point.
