药剂师 Luo 是液态爆炸物方面的专家，在他的实验室里有 $n$ 类液态药剂，每一类液态药剂都有很多副，这些药剂由四种化学元素组成, 这里依次称之为 alpha, beta, gamma, delta, 每一类药剂都只由这四种液态化学元素组成，这里我们认为第 $i$ 类药剂依次含有的这四种元素 $a_i, b_i, c_i, d_i$ 克.

药剂师 Luo 经常收到两类客户要求:

第一类是要求混合一副药剂, 依次含有 $A$, $B$, $C$, $D$ 克的 alpha, beta, gamma, delta 元素。

第二类是要求配制出能在特定环境下爆炸的药剂，环境参数为 $A$, $B$, $C$, $D$，如果一副药剂含有 $a$, $b$, $c$, $d$ 克指定元素，那么当 $A \cdot a + B \cdot b + C \cdot c + D \cdot d \geq 0$ 时，该药剂可以在此环境下引爆。

当药剂师 Luo 在混合两副药剂的时候，他可以从两副药剂中称出任意克然后进行混合。

显然有一些要求药剂师 Luo 是不可能完成的，Luo 需要你来帮忙计算这个要求是否可以完成。

输入格式

第一行一个数 $N$, 表示 Luo 有的药剂种类。

接下来 $N$ 行, 每行 $4$ 个数 $a_i$, $b_i$, $c_i$, $d_i$，代表了这个药剂四种元素的含量。

接下来一行一个数 $M$, 代表客户请求数。

接下来 $M$ 行每行五个数 $q, A, B, C, D$。

输出格式

一共 $M$ 行，依次代表每个请求是否可以完成，如果可以完成则输出 “Y”，否则输出 “N”。 (不包含引号)

4
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
4
1 1 2 3 4
1 2 1 3 4
2 1 1 1 1
2 -1 -1 -1 -1

Y
Y
Y
N

10
0 0 0 1
5289 1684 8075 24952
2609 8084 4886 24421
2737 7620 5520 24123
6574 1863 7023 24540
2510 5613 7631 24246
5942 4118 6615 23325
8861 907 4085 26147
1691 4369 8607 25333
7647 3553 4992 23808
10
2 119532316 -6307684 220972316 -99987684
1 1294 4590 4116 30000
2 1555221 -12364779 207395221 -39684779
1 6135 4007 6803 23055
1 8528 5185 615 25672
1 1118 4295 9943 24644
1 1691 4369 8607 25333
2 -73813002 193626998 178226998 -111693002
1 5941 4118 6615 23325
2 127217853 112977853 87617853 -45302147

N
N
Y
N
N
N
Y
N
Y
Y

限制与约定

对于 20% 的数据 $N, M \leq 200$；

对于 40% 的数据 $N, M \leq 4000$；

对于 60% 的数据 $N \leq 20000, M \leq 40000$；

对于 100% 的数据 $4 \leq N \leq 50000, M \leq 100000$。

$a_i, b_i, c_i, d_i, A, B, C, D$ 的绝对值小于 $10^9$。

时间限制：$4\texttt{s}$

空间限制：$256\texttt{MB}$

来源

中国国家队清华集训2014~2015 Day 3 - By 梁盾

下载

样例数据下载