Problem D
Bird Rescue
Polly the Parrot is sitting at the top of her favorite tree in Manhattan. In Manhattan, the roads are either avenues; going north to south, or streets; going east to west. The avenues are numbered $0$, $1$, $2$, and so on, from east to west, with avenue $0$ being the easternmost one. The streets are numbered $0$, $1$, $2$, etc, from south to north, with street $0$ being the southernmost one. Polly thinks that the New Yorkers were not very creative in naming their roads, but at least this naming convention makes for a convenient coordinate system.
Polly has $n$ friends that live in different parts of the city. Friend $i$ is known to never leave the neighborhood between avenue $x_1^ i$ and $x_2^ i$, and between the streets $y_1^ i$ and $y_2^ i$. Every now and then, Polly hears a call for help from one of her friends. Based on how loud the call is, Polly is able to precisely determine that the manhattan distance from her tree to the friend who is calling (in Manhattan the buildings are so tall that even sound travels along the streets and avenues). Polly doesn’t care enough to actually go help, but she is interested in how many different friends the call could be coming from. This is what she is asking you to help her with. That, and a cracker.
Input
The first input line contains two positive integers $n$ and $q$: the number of friends Polly has, and the number of calls for help she heard. The second line contains two values $x_ a$ and $y_ a$: the position of the tree where she is sitting.
Then follow $n$ lines that describe the neighborhoods her friends frequent. The $i$’th line describes the neighborhood of friend $i$ by specifying $x_1^ i, y_1^ i, x_2^ i$ and $y_2^ i$. Finally there are $q$ lines that describe the calls for help. Each line $j$ contains a single non-negative integer $x_ j \geq 0$, how far from Polly in Manhattan distance the call originated from.
We always have $1 \leq n, q \leq 10^5$. Further, all coordinates are integers and between $0$ and $10^6$, and all distances are integers between $0$ and $2\cdot 10^6$.
Output
For each call for help, output the number of friends the call for help could be coming from.
Sample Input 1 | Sample Output 1 |
---|---|
6 13 1 4 0 7 1 6 3 5 0 3 0 1 3 2 4 6 5 3 8 7 7 4 8 0 7 2 0 1 2 3 4 5 6 7 8 9 10 11 12 |
1 1 3 4 3 2 2 1 2 2 2 1 0 |