eolymp
bolt
Try our new interface for solving problems
Problems

Camouflaged camp

Camouflaged camp

\includegraphics{https://static.e-olymp.com/content/a9/a9beee3851119d3bab2b7fe18fe34d183fd25f4e.jpg} 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. 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 \begin{itemize} \item \textit{location,} i.e. the coordinates of the top-left corner of the first (i.e. the left or the top) rectangular area; The coordinates are given in respect of the camp area. \item \textit{size }(length and width) of the first (and the second because they are equal) rectangular areas; \item \textit{rectangle arrangement flag}, \textbf{0} indicates horizontal arrangement of the rectangular areas (i.e. areas have common vertical side), while \textbf{1} -- vertical arrangement (i.e. areas have common horizontal side); \item \textit{altitude flag}, \textbf{0} indicates that the average altitude of the first (i.e. the left or the top) rectangular area should be strictly less (<) than the average altitude of the second. \textbf{1} indicates the opposite (≥) situation. \end{itemize} 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. \InputFile The first line contains two integers \textbf{R} and \textbf{C} (\textbf{2} ≤ \textbf{R}, \textbf{C} ≤ \textbf{1000}). They correspond to the number of rows and columns in the topographic map. The following \textbf{R} lines with \textbf{C} nonnegative integer numbers in each of them describe the topographic map. The altitude does not exceed \textbf{255} at any coordinate. Two integer numbers \textbf{L} (number of rows) and \textbf{W} (number of columns) (\textbf{1} ≤ \textbf{L}, \textbf{W} ≤ \textbf{1000}; \textbf{L} ≤ \textbf{R}; \textbf{W} ≤ \textbf{C}) defining the size of the camp are written in the following line. The next line contains one integer \textbf{H} (\textbf{1} ≤ \textbf{H} ≤ \textbf{1000}) -- the number of characteristics. Finally, the following \textbf{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. \OutputFile The first line of the output file should contain two integers -- the coordinates of top-left corner of camp location.
Time limit 10 seconds
Memory limit 16 MiB
Input example #1
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
Output example #1
3 1
3
Source BOI-2005