Breaking Bomber

时间限制:40s      空间限制:256MB

题目描述

药剂师 Luo 是液态爆炸物方面的专家,在他的实验室里有 n 类液态药剂,每一类液态药剂都有很多副,这些药剂由四种化学元素组成, 这里依次称之为 alpha, beta, gamma, delta, 每一类药剂都只由这四种液态化学元素组成,这里我们认为第 i 类药剂依次含有的这四种元素 ai,bi,ci,di 克.
药剂师 Luo 经常收到两类客户要求:
第一类是要求混合一副药剂, 依次含有 A, B, C, D 克的 alpha, beta, gamma, delta 元素。
第二类是要求配制出能在特定环境下爆炸的药剂,环境参数为 A, B, C, D,如果一副药剂含有 a, b, c, d 克指定元素,那么当 A⋅a+B⋅b+C⋅c+D⋅d≥0 时,该药剂可以在此环境下引爆。
当药剂师 Luo 在混合两副药剂的时候,他可以从两副药剂中称出任意克然后进行混合。
显然有一些要求药剂师 Luo 是不可能完成的,Luo 需要你来帮忙计算这个要求是否可以完成。


输入格式

第一行一个数 N, 表示 Luo 有的药剂种类。
接下来 N 行, 每行 4 个数 ai, bi, ci, di,代表了这个药剂四种元素的含量。
接下来一行一个数 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

提示

对于 100% 的数据 4≤N≤50000,M≤100000。
ai,bi,ci,di,A,B,C,D 的绝对值小于 10^9。


题目来源

2015年国家集训队测试