IOI '06 - Merida, Yucatan, Mexico

Pyramid

After winning a great battle, King Jaguar wants to build a pyramid that will serve both as a monument to remember his victory and as a tomb for the brave soldiers that died in battle. The pyramid will be built in the battlefield and will have a rectangular base of a columns by b rows. Inside it, at ground level, is a smaller, rectangular chamber of c columns by d rows that will contain the corpses and weapons of the fallen soldiers.

The King's architects have surveyed the battlefield as an m columns by n rows grid and have measured the elevation of each square as an integer.

Both the pyramid and the chamber are to be built covering complete squares of the grid and with their sides parallel to those of the battlefield. The elevation of the squares of the internal chamber must remain unchanged but the remaining terrain of the base of pyramid will be leveled by moving sand from higher squares to lower ones. The final elevation of the base will be the average elevation of all the squares of the base (excluding those of the chamber). The architects are free to locate the internal chamber anywhere within the pyramid as long as they leave a wall at least one square thick surrounding the chamber.

Help the architects pick the best place to locate the pyramid and the internal chamber so that the final elevation of the base is the maximum possible for the sizes given.

The figure shows an example of the battlefield; the number in each square represents the elevation of the terrain in that particular position of the field. The gray squares represent the base of the pyramid while the surrounded white squares represent the chamber. This figure illustrates an optimal placement.

Write a program that, given the dimensions of the field, the pyramid, and the chamber along with the elevation of every square in the field, locates both the pyramid in the field and the chamber inside the pyramid so that the elevation of the base is the maximum possible.

Input

The first line contains six space-separated integers, in this order: m (3 ≤ m ≤ 1000), n (3 ≤ n ≤ 1000), a (3 ≤ am), b (3 ≤ bn), c (1 ≤ ca-2), and d (1 ≤ db-2).
n lines follow, each containing m space-separated integers. Each line describes the elevations in one row of the grid; lines are given in order from top to bottom. The integers in each row describe the elevations of squares in that row from left to right. All elevations are positive integers no more than 100.

Output

There should be two lines of output.
The first line of output should contain two space-separated integers - the column and row numbers respectively of the upper-left corner of the base of the pyramid.
The second line of output should contain two space-separated integers - the column and row numbers respectively of the upper-left corner of the chamber inside the pyramid.

Sample Input

8 5 5 3 2 1
1 5 10 3 7 1 2 5
6 12 4 4 3 3 1 5
2 4 3 1 6 6 19 8
1 1 1 3 4 2 4 5
6 6 3 3 3 2 2 2

Sample Output

4 1
6 2

Note: In test cases worth a total of 30% of the points, m and n will each be no greater than 10.

All Submissions
Best Solutions


Point Value: 25 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: Aug 01, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

For some cases, the judge tells me that my program TLE'd yet it displayed output from my program.
Is this because the judge allows the program a little bit of extra time?

Your output may have been implicitly flushed, I think.

Though I could be (read: probably am) wrong.

It could be; I'm not exactly sure. It's possible that we let the program run for 1.1 s but show TLE if it takes more than 1.0 s. Although, IIRC, if you get TLE but you also print the right answer, you still get points for that test case.

But if he TLE'd and printed the right answer, then he wouldn't have been displayed output, so...

Yeah, the answer is still wrong.