Square Queries

There is a grid with $H$ rows and $W$ columns. Each cell is denoted $(i, j)$, meaning the cell in row $i$ from the top and column $j$ from the left. Cell $(i, j)$ contains an integer $A_{ij}$, and each value satisfies $1 \le A_{ij} \le H \times W$.

An integer $K$ and $Q$ queries are given. Each query gives coordinates $(y, x)$, which denote a square with its top-left cell at $(y, x)$ and side length $K$. For each query, erase the numbers in the cells inside the given square, then count the distinct numbers in the remaining cells of the grid.

All queries are independent. A previous query does not affect the next one.

The first line contains $H$, $W$, $K$, and $Q$. ($1 \le H, W \le 2\,000$, $1 \le K \le \min(H, W)$, $1 \le Q \le 3 \times 10^5$)

The next $H$ lines each contain $W$ integers $A_{ij}$, separated by spaces. ($1 \le A_{ij} \le H \times W$)

The next $Q$ lines each contain two integers $y$ and $x$, the top-left cell of the square. ($1 \le y \le H - K + 1$, $1 \le x \le W - K + 1$)

For each query, print on its own line the number of distinct values in the grid that remain after removing the given square.