Problem 5096. -- [SWERC2017]Table

5096: [SWERC2017]Table

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board]

Description

在一张X*Y的矩形格子桌子上放置着N个装饰物。
每个装饰物都占据着若干个完整的格子,且都可以看作平行坐标轴的矩形。
当然,它们不能互相重叠,但是可以互相接触。
给定D个询问,每个询问将给定一个新的装饰物
你需要输出如果将它放到桌子上,且不和之前N个装饰物重叠,且四个顶点都是格点,四边平行坐标轴的话,有多少种可行的方案?
注意装饰物不能旋转90度。

Input

第一行包含四个整数X,Y,N,D(1<=X,Y<=2000,0<=N<=1000000,1<=D<=100000),表示桌子的尺寸、装饰品的个数以及询问次数。
接下来N行,每行4个整数x,x',y,y'(0<=x<x'<=X,0<=y<y'<=Y),描述每个装饰物的两个对顶点的坐标。
接下来D行,每行两个正整数x,y(1<=x<=X,1<=y<=Y),表示一个询问装饰物的尺寸。

Output

输出D行,每行一个整数,即合法的位置个数。

Sample Input

7 5 3 9
1 2 0 1
5 7 2 5
0 1 2 4
7 1
3 5
5 3
2 2
3 3
4 4
4 5
6 2
1 1

Sample Output

1
1
0
13
5
1
0
0
26

HINT

Source

[Submit][Status]