19070번 - Criminals 다국어

In an ancient country, there are $n \times m$ cities, labeled by integers from $1$ to $n \cdot m$. The coordinates of the city labeled by $(x - 1) \cdot m + y$ are $(x, y)$ ($1 \leq x \leq n$, $1 \leq y \leq m$). There are $q$ tourists. Initially, the $i$-th tourist is at city ($x_i, y_i$). All tourists want to go out and play in other cities.

Unfortunately, $K$ of the $n \cdot m$ cities are controlled by  criminals, so these $K$ cities are unsafe. For safety reasons, a tourist whose initial coordinates are $(x_1, y_1)$ can go to the city $(x_2, y_2)$ if and only if all of the cities $(x, y)$ ($\min (x_1, x_2) \leq x \leq \max (x_1, x_2)$, $\min (y_1, y_2) \leq y \leq \max (y_1, y_2)$) are safe.

Now, for each tourist, calculate the number of cities they can reach safely (including their initial city).

The first line of the input contains four integers $n$, $m$, $K$ and $q$ ($1 \leq n, m, K, q \leq 10^5$).

Then $K$ lines follow. Each of these lines contains two integers $a_i$ and $b_i$: the coordinates of an unsafe city ($1 \leq a_i \leq n$, $1 \leq b_i \leq m$). It is guaranteed that each city appears at most once in this list.

Then $q$ lines follow. Each of these lines contains two integers $x_i$ and $y_i$: the initial city of each tourist ($1 \leq x_i \leq n$, $1 \leq y_i \leq m$). It is guaranteed that, initially, each tourist stays at a safe city.

For each tourist, print a single line with a single integer: the number of cities this tourist can reach safely.

In the example, the third tourist can reach eight cities: $(1, 4)$, $(2, 4)$, $(3, 4)$, $(4, 4)$, $(1, 3)$, $(2, 3)$, $(2, 2)$ and $(2, 1)$.