정사각형과 쿼리

$H$개의 행과 $W$개의 열로 이루어진 격자가 있다. 각 격자 칸은 $(i, j)$로 나타내며, 위에서부터 $i$번째 행, 왼쪽에서부터 $j$번째 열을 뜻한다. 칸 $(i, j)$에는 정수 $A_{ij}$가 적혀 있으며, 이 값은 $1$ 이상 $H \times W$ 이하이다.

정수 $K$와 $Q$개의 쿼리가 주어진다. 각 쿼리는 좌표 $(y, x)$를 준다. 이는 왼쪽 위 칸이 $(y, x)$이고 한 변의 길이가 $K$인 정사각형을 뜻한다. 각 쿼리마다 주어진 정사각형 안의 칸에 적힌 수를 모두 지웠을 때, 나머지 격자 칸에 존재하는 서로 다른 수의 개수를 구하여라.

모든 쿼리는 독립적이다. 이전 쿼리는 다음 쿼리에 영향을 주지 않는다.

첫 번째 줄에 $H$, $W$, $K$, $Q$가 주어진다. ($1 \le H, W \le 2\,000$, $1 \le K \le \min(H, W)$, $1 \le Q \le 3 \times 10^5$)

다음 $H$개의 줄에는 $W$개의 정수 $A_{ij}$가 공백으로 구분되어 주어진다. ($1 \le A_{ij} \le H \times W$)

이후 $Q$개의 줄에는 정수 $y$와 $x$가 주어진다. $(y, x)$는 정사각형의 왼쪽 위 칸의 좌표이다. ($1 \le y \le H - K + 1$, $1 \le x \le W - K + 1$)

각 쿼리마다 주어진 정사각형을 제외한 나머지 격자 칸에 존재하는 서로 다른 수의 개수를 한 줄에 하나씩 출력한다.