L. Late and Disobedient
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nathan is running late to the annual meeting of the Public Disobedience Association (PDA). He was driving there as fast as he could until he got stuck in front of a red light. As he is in a hurry, he wants to cross the street anyway (see Disclaimer). Of course, Nathan is not a monster, so he will cross the street only if there is enough space to cross it without hurting any pedestrian. At a given time $$$T$$$, Nathan has the "feeling" that he could cross the street safely, but Nathan's feelings can be completely wrong!

The crosswalk has length $$$L$$$ and can be modeled as a segment on the $$$x$$$-axis with endpoints at $$$x = 0$$$ and $$$x = L$$$. There are $$$N$$$ pedestrians on the $$$x$$$-axis, not necessarily on the crosswalk. Each pedestrian has an initial position $$$X$$$ and a constant velocity $$$V$$$ (positive or negative); this means that at each time $$$t \ge 0$$$ the position of the pedestrian is $$$X + t \cdot V$$$.

Nathan's car has width $$$C$$$ and he can cross the street if there is a gap of width at least $$$C$$$ between two consecutive pedestrians on the crosswalk or between a pedestrian and an endpoint of the crosswalk. He can also cross if there are no pedestrians on the crosswalk.

You will be given $$$Q$$$ queries. Each query specifies an integer time $$$T \ge 0$$$ and you must decide whether Nathan can cross the street at that moment. Disclaimer: The organization of Programadores de América (PDA) does not condone crossing red lights nor breaking the law. This is a fictional story and the behavior of Nathan does not represent the opinions of the organization of the competition.

Input

The first line contains three integers $$$N$$$, $$$C$$$ and $$$L$$$ ($$$1 \le N \le 1000$$$ and $$$1 \le C \le L \le 10^{9}$$$), indicating respectively the number of pedestrians, the width of Nathan's car and the length of the crosswalk.

Each of the next $$$N$$$ lines describes a pedestrian with two integers $$$X$$$ and $$$V$$$ ($$$-10^{9} \le X, V \le 10^{9}$$$ and $$$V \neq 0$$$), representing respectively the initial position and velocity of the pedestrian. No two pedestrians have the same initial position and velocity (they differ in at least one of them). The next line contains an integer $$$Q$$$ ($$$1 \leq Q \leq 2 \times 10^{6}$$$) denoting the number of queries.

Each of the next $$$Q$$$ lines contains an integer $$$T$$$ ($$$0 \le T \le 10^{9}$$$) indicating the time to be considered. Times are given in increasing order.

Output

Output a line for each query, with the uppercase letter "Y" if Nathan can cross the street at the corresponding time, and the uppercase letter "N" otherwise.

Example
Input
4 5 10
1 1
9 -1
-1 -1
11 1
3
0
3
4
Output
Y
N
Y
Note

Explanation for example 1

In this sample there are $$$N=4$$$ pedestrians, Nathan's car has width $$$C=5$$$, and the crosswalk has length $$$L=10$$$.

At time $$$T=0$$$ the pedestrians are at positions $$$x_1=1$$$, $$$x_2=9$$$, $$$x_3=-1$$$ and $$$x_4=11$$$, so Nathan can cross the street because there is a gap of width at least $$$5$$$ between $$$x_1=1$$$ and $$$x_2=9$$$.

At time $$$T=3$$$ the pedestrians are at positions $$$x_1=4$$$, $$$x_2=6$$$, $$$x_3=-4$$$ and $$$x_4=14$$$, so Nathan cannot cross the street because no gap is wide enough.

Finally, at time $$$T=4$$$ the pedestrians are at positions $$$x_1=x_2=5$$$, $$$x_3=-5$$$ and $$$x_4=15$$$, so Nathan can cross the street using either the gap between $$$x=0$$$ and $$$x_1=x_2=5$$$, or the gap between $$$x_1=x_2=5$$$ and $$$x=L=10$$$.