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