Vaccination

Time limit: 0.25s Memory limit: 64MB Input: Output:

The glorious team at V.R.N.C. have developed a vaccine against the latest illness. The vaccine starts at one individual and spreads itself to his 44 neighbours (assuming the population is accurately represented by an nmn \cdot m matrix). After that each person will again spread its vaccine to the 44 neighbours and that will keep happening until a person on the border is vaccinated, at which point it suddenly stops spreading. Considering a 666 \cdot 6 matrix where 11 means vaccinated and 00 means not vaccinated the spread may look like this:

000000000000000000000100000000000000  000000000000000100001110000100000000  000000000100001110011111001110000100\begin{matrix} 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&1&0&0\\ 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ \end{matrix} \Large \ \rightarrow \ \normalsize \begin{matrix} 0&0&0&0&0&0\\ 0&0&0&0&0&0\\ 0&0&0&1&0&0\\ 0&0&1&1&1&0\\ 0&0&0&1&0&0\\ 0&0&0&0&0&0\\ \end{matrix} \Large \ \rightarrow \ \normalsize \begin{matrix} 0&0&0&0&0&0\\ 0&0&0&1&0&0\\ 0&0&1&1&1&0\\ 0&1&1&1&1&1\\ 0&0&1&1&1&0\\ 0&0&0&1&0&0\\ \end{matrix}

After 33 iterations the spread stops and only 1313 people have been vaccinated. Your task is given the matrix of people and the value in each cell representing the age of each person, calculate the point where V.R.N.C. should initiate the vaccine to maximize the sum of the ages of all vaccinated people.

Input data

The first line will contain two integers nn and mm.

The following nn lines will contain mm integers each.

Output data

The first line will contain two integers ii and jj where the simulation should start.

If there are multiple solutions print the one with the smallest ii. In case of equality again print the solution with the smallest jj.

Constraints and clarifications

  • 1n,m1 0001 \leq n, m \leq 1 \ 000;
  • 0aij<2320 \leq a_{ij} < 2^{32}

Example 1

stdin

3 4
1 2 3 4
5 6 7 8
9 10 11 12

stdout

2 3

Explanation

Starting at cell (2,32, 3) with value 77 the spread will also reach values 33, 66, 88 and 1111 and the sum will be 3535, the maximum possible sum given any starting point.

Log in or sign up to be able to send submissions!