시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 12 | 1 | 1 | 33.333% |
Squad commander is looking for a location to build a camouflaged camp of a certain size. He has a digital topographic map of the area, which is a rectangular grid with every element defining the altitude at a certain coordinate. Coordinates of any point on the map are identified by the row and the column in the table.
Digital topographic 5x6 map Camp of size 3×5 at position (3,2)
The camp location should be a rectangle fully located within the map area and satisfy certain characteristics. Each characteristic consists of two identical adjacent rectangular areas and the requirement for their altitudes. It is defined by
Characteristic A:
The selected location satisfies characteristic A. |
Characteristic B:
The selected location does not satisfy characteristic B. |
The camp location satisfies the characteristic if the altitude requirement is satisfied.
Write a program which given the topographic map of the area and the characteristics would find the best (the one that satisfies most characteristics) location for building the camouflaged camp. In case of several solutions, output any of them.
The first line contains two integers R and C (2 ≤ R, C ≤ 1000). They correspond to the number of rows and columns in the topographic map. The following R lines with C nonnegative integer numbers in each of them describe the topographic map. The altitude does not exceed 255 at any coordinate.
Two integer numbers L (number of rows) and W (number of columns) (1 ≤ L, W ≤ 1000; L ≤ R; W ≤ C) defining the size of the camp are written in the following line.
The next line contains one integer H (1 ≤ H ≤ 1000) – the number of characteristics.
Finally, the following H lines describe characteristics. Each of them contains 6 integers: coordinates of the characteristic’s top-left corner, size of the first rectangular area, the arrangement and the altitude flags. All characteristics fit within the camp.
The first line should contain two integers – the coordinates of top-left corner of camp location.
5 6 2 2 2 2 2 2 2 6 6 4 3 2 3 5 8 7 7 4 4 6 8 9 8 6 5 7 8 8 8 7 3 5 3 1 1 1 3 1 0 2 2 2 2 0 0 2 4 1 1 1 1
3 1
Location (3, 1) satisfies all three characteristics