Rikka with Terrorist

Problem Description

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 \times m$ cities. The coordinate of the $(x-1)m+y$th city is $(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)$ and all of them want to go out and play in other cities. Unfortunately, $K$ of the $n \times 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) \leq x \leq \max(x1,x2),\min(y1,y2) \leq y \leq \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)$.

Input

The first line contains a number $t(1 \leq t \leq 100)$, the number of the testcases. There are at least $98$ testcases with $n,m,K,q \leq 10^3$. For each testcase, the first line contains four numbers $n,m,K,q(1 \leq n,m,K,q \leq 10^5)$.

Then $K$ lines follow, each line contains two numbers $(a_i,b_i)(1 \leq a_i \leq n,1 \leq b_i \leq 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 $(x_i,y_i)(1 \leq x_i \leq n,1 \leq y_i \leq m)$ -- the initial city of each tourist. It is guaranteed that initially each tourist stays at a safe city.

Output

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

Sample Input

1
4 5 4 4
1 2
2 5
3 3
4 5
1 5
2 1
2 4
4 1

Sample Output

3
9
8
9

Source

2017 Multi-University Training Contest - Team 5

https://acm.hdu.edu.cn/showproblem.php?pid=6089