Camouflaged camp#3015
The 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 where each element denotes the altitude at a specific coordinate. Coordinates of any point on the map are defined by the row and column in the table.
The camp location should be a rectangle fully within the map area and should satisfy certain characteristics. Each characteristic consists of two identical adjacent rectangular areas and a requirement on their altitudes. Each characteristic is defined by:
Location, i.e., the coordinates of the top-left corner of the first (left or top) rectangular area; the coordinates are given relative to the camp area.
Size (length and width) of the first (and the second, since they are equal) rectangular areas;
Rectangle arrangement flag: 0 indicates horizontal arrangement (areas share a vertical side), 1 indicates vertical arrangement (areas share a horizontal side);
Altitude flag: 0 means the average altitude of the first (left or top) rectangular area must be strictly less () than the second; 1 indicates the opposite () requirement.
The camp location meets a characteristic if the altitude requirement is satisfied.
Write a program that, given the topographic map and the characteristics, finds the best location (i.e., one that satisfies the largest number of characteristics) for building the camouflaged camp. If there are multiple solutions, output any of them.
The first line contains two integers and (2 \leq R, C \leq 1000) — the number of rows and columns in the topographic map. The following lines, each with non-negative integers, describe the topographic map. The altitude at any coordinate does not exceed .
The next line contains two integers (number of rows) and (number of columns) (1 \leq L, W \leq 1000; L \leq R; W \leq C) specifying the size of the camp.
The next line contains one integer (1 \leq H \leq 1000) — the number of characteristics.
Each of the next lines describes a characteristic. Each line contains integers: the coordinates of the characteristic's top-left corner, the size of the first rectangular area, the arrangement, and the altitude flags. All characteristics fit within the camp.
The first line of the output should contain two integers — the coordinates of the top-left corner of the camp location.
Example 1