위장 캠프

분대장은 정해진 크기의 위장 캠프를 세울 위치를 찾고 있다. 그는 이 지역의 디지털 지형도를 가지고 있는데, 지형도는 각 칸이 그 좌표의 고도를 나타내는 직사각형 격자이다. 격자의 각 칸은 행 번호와 열 번호로 지정하며, 행과 열은 모두 1부터 센다.

3×5 크기의 캠프를 위치 (3, 2)에 놓은 5×6 지형도.

캠프는 지형도 안에 완전히 들어가야 하는 L × W 직사각형이다(L은 행 수, W는 열 수). 캠프의 위치는 지형도 위에서 캠프의 왼쪽 위 칸의 좌표 (행, 열)로 나타낸다.

각 후보 위치는 여러 특성(characteristic) 으로 평가한다. 하나의 특성은 캠프 안에 있는, 크기가 같고 서로 맞닿은 두 직사각형 영역을 비교하며 다음으로 정의된다.

• 위치 — 첫 번째 영역의 왼쪽 위 칸의 좌표 (행, 열). 이 좌표는 캠프를 기준으로 하며, 캠프 자신의 왼쪽 위 칸이 (1, 1)이다.
• 크기 — 각 영역의 행 수와 열 수(두 영역의 크기는 같다).
• 배치 플래그 — 0이면 두 영역이 가로로 나란히 놓이고(세로 변을 공유하므로 두 번째 영역이 첫 번째 영역의 바로 오른쪽에 있다), 1이면 세로로 쌓인다(가로 변을 공유하므로 두 번째 영역이 첫 번째 영역의 바로 아래에 있다).
• 고도 플래그 — 0이면 첫 번째 영역의 평균 고도가 두 번째 영역의 평균 고도보다 엄격히 작을 때(<) 특성을 만족하고, 1이면 첫 번째 영역의 평균 고도가 두 번째 영역보다 크거나 같을 때(≥) 만족한다.

두 영역의 칸 수는 항상 같으므로, 평균 고도를 비교하는 것은 각 영역의 고도 합을 비교하는 것과 같다.

특성 A — 위치 (1, 1), 크기 (1, 3), 배치 플래그 1, 고도 플래그 0. 위 그림의 캠프 위치는 이 특성을 만족한다.

특성 B — 위치 (2, 2), 크기 (2, 2), 배치 플래그 0, 고도 플래그 0. 위 그림의 캠프 위치는 이 특성을 만족하지 않는다.

지형도, 캠프 크기, 특성 목록이 주어질 때, 가능한 한 많은 특성을 만족하는 캠프 위치를 찾아라.

• 첫째 줄에 두 정수 R과 C가 주어진다 (2 ≤ R, C ≤ 1000). 지형도의 행 수와 열 수이다.
• 다음 R개의 줄에는 각각 C개의 음이 아닌 정수가 주어진다. i행 j열의 값은 그 좌표의 고도이며 255를 넘지 않는다.
• 다음 줄에 두 정수 L과 W가 주어진다 (1 ≤ L ≤ R, 1 ≤ W ≤ C). 캠프의 행 수와 열 수이다.
• 다음 줄에 정수 H가 주어진다 (1 ≤ H ≤ 1000). 특성의 개수이다.
• 다음 H개의 줄에는 각각 한 특성을 나타내는 여섯 정수가 주어진다. 순서대로 첫 번째 영역의 왼쪽 위 칸의 행과 열(캠프 기준), 각 영역의 행 수와 열 수, 배치 플래그, 고도 플래그이다. 모든 특성은 캠프 안에 완전히 들어간다.

가장 많은 특성을 만족하는 캠프 위치의 왼쪽 위 칸의 (지형도 기준) 행과 열, 두 정수를 출력한다.

그러한 최댓값을 만족하는 위치가 여럿이면 사전순으로 가장 작은 위치를 출력한다. 즉 행이 가장 작은 것을, 행이 같으면 열이 가장 작은 것을 출력한다.