Замаскований табір
Командир загону шукає місце для розміщення замаскованого табору певного розміру. У його розпорядженні є цифрова топографічна карта місцевості, яка представлена у вигляді прямокутної сітки, де кожен елемент вказує на висоту в певній точці. Координати будь-якої точки на карті визначаються рядком і стовпцем у таблиці.
Місце для табору повинно бути прямокутником, повністю розташованим у межах карти, і відповідати певним характеристикам. Кожна характеристика складається з двох однакових суміжних прямокутних областей та вимоги до їх висот. Вона визначається:
розташуванням, тобто координатами верхнього лівого кута першої (тобто лівої або верхньої) прямокутної області; координати задані відносно області табору;
розміром (довжина і ширина) першої (і другої, оскільки вони рівні) прямокутних областей;
прапором розташування прямокутника, де 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 цілих чисел: координати верхнього лівого кута характеристики, розмір першої прямокутної області, прапор розташування і прапор висоти. Усі характеристики вміщуються в межах табору.
Вихідні дані
Перший рядок вихідного файлу повинен містити два цілі числа – координати верхнього лівого кута місця розташування табору.