Nash equilibrium

2000ms

262144K

Description:

This is an unusual problem in an unusual contest, here is the announcement: http://codeforces.com/blog/entry/73543

You are given a table $$$A$$$ of integers $$$n \times m$$$. The cell $$$(x, y)$$$ is called Nash equilibrium if both of the following conditions hold:

for each $$$x_1 \neq x$$$ $$$A_{xy} > A_{x_1y}$$$;
for each $$$y_1 \neq y$$$ $$$A_{xy} < A_{xy_1}$$$.

Find a Nash equilibrium in $$$A$$$. If there exist several equilibria, print the one with minimum $$$x$$$. If still there are several possible answers, print the one with minimum $$$y$$$.

Input:

The first line contains two integers $$$n, m$$$ ($$$2 \leq n, m \leq 1000$$$), denoting the size of the table.

Each of next $$$n$$$ lines contain $$$m$$$ space-separated integers $$$A_{ij}$$$ ($$$1 \leq A_{ij} \leq 10^9$$$).

Output:

Output $$$x$$$ and $$$y$$$ — the coordinates of the lexicographically minimum Nash equilibrium in the table. In case there is no answer, print two zeroes instead.

Sample Input:

Sample Output:

1 4

Sample Input:

Sample Output:

0 0

Informação

Provedor Codeforces

Código CF1302A