정사각형과 쿼리

$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$)

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