|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||7||5||5||100.000%|
After Doc's return from 1885 using time train, he is now excited to try other means of transportation as time machines, so he has created the time airplane! But during the first test of the time airplane, its engines failed, and the airplane crashed. Doc has ejected himself from the cabin and successfully landed using safety parachute, but the airplane has fallen down to a large field and shattered into small parts.
Now the parts of the crashed airplane need to be evacuated and recycled. Marty has drawn the plan of the field, it is a rectangle with n rows and m columns. Each cell of the rectangle contains zero or more parts of the airplane. Marty has decided to put recycling plant at one cell of the field, and bring all parts of the airplane to that cell. A special Doc's robot will bring all parts of the airplane to the recycling plant. The robot can perform the following three actions:
The robot will start from the cell where the recycling plant is located.
Now Marty needs to find out what cell should be used to build the recycling plant to minimize the number of robot's actions to recycle all the airplane parts. Help him!
The first line contains integers n and m (1 ≤ n·m ≤ 106) — the size of the field.
The i-th of the following lines contains the description of the i-row of the field: m integers ai, j (0 ≤ ai, j ≤ 106) — the number of airplane parts in the corresponding field cell.
Print three integers: r, c and x (1 ≤ r ≤ n, 1 ≤ c ≤ m) — row and column of the optimal position of the recycling plant and the total number of actions that the robot needs to recycle all the airplane parts. If there are several optimal positions for the recycling plant, print any of them.
3 3 0 0 0 0 1 0 0 0 0
2 2 2
3 3 2 0 0 0 0 0 0 2 0
2 1 20