题目描述

Nathan 正赶往公共不服从协会（PDA）的年度会议，已经迟到了。他以尽可能快的速度开车前往，却在红灯前被堵住了。由于时间紧迫，他还是想横穿马路（见免责声明）。当然，Nathan 并非蛮不讲理的人，只有在不伤害任何行人的足够空间时他才会横穿。在某个时刻 $T$，Nathan “感觉” 自己可以安全地过马路，但他的感觉可能完全错误！

人行横道长 $L$，可以建模为 $x$ 轴上从 $x = 0$ 到 $x = L$ 的一条线段。共有 $N$ 个行人在 $x$ 轴上，不一定位于人行横道上。每个行人有一个初始位置 $X$ 和一个恒定速度 $V$（正或负），这意味着在任意时间 $t \ge 0$，该行人的位置为 $X + t \cdot V$。

Nathan 的车宽为 $C$。如果人行横道上两个相邻行人之间，或者行人与横道端点之间的间隙宽度至少为 $C$，他就可以穿过马路。如果人行横道上没有行人，他也可以穿过。

你将收到 $Q$ 个查询。每个查询给出一个整数时间 $T \ge 0$，你需要判断 Nathan 能否在该时刻横穿马路。

免责声明：美洲程序员组织（PDA）不纵容闯红灯或违法行为。这是一个虚构故事，Nathan 的行为不代表该竞赛组织的观点。

输入格式

第一行包含三个整数 $N$、$C$ 和 $L$（$1 \le N \le 1000$，$1 \le C \le L \le 10^9$），分别表示行人的数量、Nathan 汽车的车宽以及人行横道的长度。

接下来 $N$ 行，每行描述一个行人，包含两个整数 $X$ 和 $V$（$-10^9 \le X, V \le 10^9$，$V \neq 0$），分别表示该行人的初始位置和速度。没有两个行人的初始位置和速度完全相同（至少有一个不同）。

下一行包含一个整数 $Q$（$1 \le Q \le 2 \times 10^6$），表示查询的数量。

接下来的 $Q$ 行，每行包含一个整数 $T$（$0 \le T \le 10^9$），表示要考察的时刻。给出的时间按递增顺序排列。

输出格式

对于每个查询输出一行，如果 Nathan 能在对应时刻横穿马路，则输出大写字母 “Y”，否则输出大写字母 “N”。

4 5 10
1 1
9 -1
-1 -1
11 1
3
0
3
4

Y
N
Y

提示

样例 1 解释：

该样例中 $N = 4$ 个行人，Nathan 车宽 $C = 5$，人行横道长 $L = 10$。

在 $T = 0$ 时刻，行人的位置分别为 $x_1 = 1$、$x_2 = 9$、$x_3 = -1$、$x_4 = 11$，因此 Nathan 可以横穿，因为 $x_1 = 1$ 与 $x_2 = 9$ 之间存在宽度至少为 $5$ 的间隙。

在 $T = 3$ 时刻，行人的位置分别为 $x_1 = 4$、$x_2 = 6$、$x_3 = -4$、$x_4 = 14$，此时没有足够宽的间隙，Nathan 无法横穿。

最后，在 $T = 4$ 时刻，行人的位置分别为 $x_1 = x_2 = 5$、$x_3 = -5$、$x_4 = 15$，Nathan 可以利用 $x = 0$ 与 $x_1 = x_2 = 5$ 之间的间隙，或者 $x_1 = x_2 = 5$ 与 $x = L = 10$ 之间的间隙横穿马路。

翻译由 DeepSeek V4 Pro 完成