ACM-ICPC-OJ训练营

问题 E: Rikka with Terrorist

时间限制: 12 Sec 内存限制: 128 MB
提交: 1 解决: 1
[提交][状态][讨论版][命题人:]

题目描述

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

In an ancient country, there are

n×m cities. The coordinate of the

(x−1)m+yth city is

(x,y)(1≤x≤n,1≤y≤m). There are

q tourists. Initially, the

ith tourist is at city

(xi,yi) and all of them want to go out and play in other cities.

Unfortunately,

K of the

n×m cities has been controlled by terrorists, so these

K cities became unsafe. For safety, the tourist whose initial coordinate is

(x1,y1) can go to the city

(x2,y2) if and only if all of the city

(x,y)(min(x1,x2)≤x≤max(x1,x2),min(y1,y2)≤y≤max(y1,y2)) is safe.

Now, for each tourist, Yuta wants to know the number of cities he can reach safely (including the initial city he stayed).

It is too difficult for Rikka. Can you help her?

In the sample, the third tourist can reach

(1,4),(2,4),(3,4),(4,4),(1,3),(2,3),(2,2),(2,1).

输入描述

The first line contains a number

t(1≤t≤100), the number of the testcases. There are at least

98 testcases with

n,m,K,q≤103.

For each testcase, the first line contains four numbers

n,m,K,q(1≤n,m,K,q≤105).

Then

K lines follow, each line contains two numbers

(ai,bi)(1≤ai≤n,1≤bi≤m) -- the coordinate of an unsafe city. It is guaranteed that the coordinates are different from each other.

Then

q lines follow, each line contains two numbers

(xi,yi)(1≤xi≤n,1≤yi≤m) -- the initial city of each tourist. It is guaranteed that initially each tourist stays at a safe city.

输出描述

For each tourist, print a single line with a single number -- the answer.

样例输入

样例输出