33908번 - 지형 평탄화 탐색기

문제

(주)영일소프트는 지형의 고도차가 심한 지역에 도시 기반 시설을 구축하기 위한 건설 시뮬레이션 시스템을 개발하고 있다.

이 시스템에서는 두 가지 핵심 정보가 사용된다.

• 지도: 해당 지역의 지형에 대한 고도를 기록한 $N \times M$ 크기의 격자판으로, 각 지점의 현재 고도 정보를 가지고 있다.
• 작업 계획도: $r \times c$ 크기의 격자판으로, 각 칸에는 얼마만큼의 높이를 줄여야 하는지 적혀있다.

지도에서 $r \times c$ 크기의 격자 영역을 선택하여 작업 계획도와 정확히 겹치도록 한 후, 각 지점에 대해 지도에 적힌 고도에서 작업 계획도에 적힌 값을 빼보았을 때, 해당 격자 영역 내 모든 지점의 고도가 동일해진다면 해당 위치는 평탄화가 가능한 부지로 판단한다. 단, 작업 계획도를 회전하거나 변형할 수 없으며, 주어진 형태 그대로 적용해야 한다. 음수의 고도로도 평탄화가 가능함에 유의한다.

사용자는 다양한 작업 계획도를 생성하거나, 지도에서 특정 지점의 고도를 직접 수정해 가며 평탄화가 가능한 부지를 탐색한다. 이러한 작업을 반복하면서 도시 건설이 가능한 부지를 시뮬레이션하고, 최적의 부지 후보를 확보하는 것이 목표다.

프로그램은 다음과 같은 $Q$개의 쿼리를 처리해야 한다.

• 1ドル\ x\ y\ h$
  • 지도에서 $x$번째 행, $y$번째 열의 고도를 $h$로 수정한다. $(1 \leq h \leq 5)$
• 2ドル\ r\ c\ a_{1,1}\ a_{1,2}\ ...\ a_{r,c}$
  • $r \times c$ 크기의 작업계획도가 주어진다. $i$번째 행, $j$번째 열에 해당하는 칸에는 줄여야 하는 고도 값 $a_{i,j}$가 기록되어 있다. 이 계획도를 지도 위의 모든 가능한 위치에 적용해 보면서, 해당 부지가 평탄화 가능한지를 확인한다. 그 결과로, 평탄화가 가능한 부지의 총 개수를 출력한다. $(0 \leq a_{i,j} \leq 5;$ 1ドル \leq r \leq \min(9,N);$ 1ドル \leq c \leq \min(9,M);$ $\ 1 \leq r \times c \leq 9)$

입력

첫 번째 줄에 지도의 행의 개수와 열의 개수를 나타내는 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다. $(1 \leq N, M \leq 500)$

두 번째 줄부터 $N$개의 줄에 걸쳐 지도의 고도 정보가 주어진다. 각 줄은 한 행에 해당하며, $M$개의 정수가 공백으로 구분되어 주어진다. 이 정수들은 해당 행의 첫 번째 열부터 $M$번째 열까지의 해발 고도를 의미하며, 1ドル$ 이상 5ドル$ 이하의 정수이다.

그다음 줄에는 쿼리의 개수를 나타내는 정수 $Q$가 주어진다. 2번 쿼리는 최소 한 번 이상 주어진다. $(1 \leq Q \leq 100,000円)$

이후 $Q$개의 줄에 걸쳐 한 줄에 하나씩 쿼리가 주어진다.

출력

2번 쿼리가 주어질 때마다 그 결과를 한 줄에 하나씩 출력한다.

제한

힌트