Замаскированный лагерь
Командир отряда ищет подходящее место для строительства замаскированного лагеря определенного размера. У него есть цифровая топографическая карта местности, представляющая собой прямоугольную сетку, где каждый элемент указывает высоту в конкретной точке. Координаты любой точки на карте определяются строкой и столбцом в таблице.
Место для лагеря должно быть прямоугольником, полностью находящимся в пределах карты, и соответствовать определенным характеристикам. Каждая характеристика состоит из двух одинаковых смежных прямоугольных областей и требования к их высотам. Она определяется:
расположением, то есть координатами верхнего левого угла первой (то есть левой или верхней) прямоугольной области; координаты даны относительно области лагеря;
размером (длина и ширина) первой (и второй, так как они равны) прямоугольных областей;
флагом расположения прямоугольников, где 0 указывает на горизонтальное расположение прямоугольных областей (то есть области имеют общую вертикальную сторону), а 1 — вертикальное расположение (то есть области имеют общую горизонтальную сторону);
флагом высоты, где 0 указывает, что средняя высота первой (то есть левой или верхней) прямоугольной области должна быть строго меньше (<), чем средняя высота второй. 1 указывает на противоположную (≥) ситуацию.
Место для лагеря удовлетворяет характеристике, если требование по высоте выполнено.
Напишите программу, которая, имея топографическую карту местности и характеристики, найдет лучшее (удовлетворяющее наибольшему количеству характеристик) место для строительства замаскированного лагеря. В случае нескольких решений, выведите любое из них.
Входные данные
Первая строка содержит два целых числа R и C (2 ≤ R, C ≤ 1000). Они соответствуют количеству строк и столбцов на топографической карте. Следующие R строк с C неотрицательными целыми числами в каждой из них описывают топографическую карту. Высота не превышает 255 на любой координате.
Два целых числа L (количество строк) и W (количество столбцов) (1 ≤ L, W ≤ 1000; L ≤ R; W ≤ C) определяют размер лагеря и записаны в следующей строке.
Следующая строка содержит одно целое число H (1 ≤ H ≤ 1000) — количество характеристик.
Наконец, следующие H строк описывают характеристики. Каждая из них содержит 6 целых чисел: координаты верхнего левого угла характеристики, размер первой прямоугольной области, флаги расположения и высоты. Все характеристики помещаются в пределах лагеря.
Выходные данные
Первая строка выходного файла должна содержать два целых числа — координаты верхнего левого угла расположения лагеря.