Description
Pharmacist Luo is an expert in liquid explosives. In his laboratory, there are $n$ types of liquid potions, and there are many units of each type. These potions are composed of four chemical elements, which we will call alpha, beta, gamma, and delta, respectively. Each type of potion consists only of these four liquid chemical elements. Here, we consider that one unit of the $i$-th type of potion contains $a_i, b_i, c_i, d_i$ grams of these four elements, respectively.
Pharmacist Luo often receives two types of customer requests:
The first type is a request to mix a potion that contains $A, B, C, D$ grams of alpha, beta, gamma, and delta elements, respectively.
The second type is a request to prepare a potion that can explode in a specific environment. The environmental parameters are $A, B, C, D$. If a potion contains $a, b, c, d$ grams of the specified elements, it can be detonated in this environment if $A \cdot a + B \cdot b + C \cdot c + D \cdot d \geq 0$.
When Pharmacist Luo mixes two potions, he can weigh out any amount (in grams) from each of the two potions and then mix them.
Obviously, some requests are impossible for Pharmacist Luo to fulfill. Luo needs you to help calculate whether each request can be fulfilled.
Input
The first line contains a number $N$, representing the number of potion types Luo has.
The next $N$ lines each contain 4 numbers $a_i, b_i, c_i, d_i$, representing the content of the four elements in that potion.
The next line contains a number $M$, representing the number of customer requests.
The next $M$ lines each contain five numbers $q, A, B, C, D$.
Output
A total of $M$ lines, each representing whether the corresponding request can be fulfilled. If it can be fulfilled, output "Y"; otherwise, output "N". (Quotes not included)
Examples
input
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
output
Y Y Y N
Examples
input
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
output
N N Y N N N Y N Y Y
Constraints
For 20% of the data, $N, M \leq 200$;
For 40% of the data, $N, M \leq 4000$;
For 60% of the data, $N \leq 20000, M \leq 40000$;
For 100% of the data, $4 \leq N \leq 50000, M \leq 100000$.
The absolute values of $a_i, b_i, c_i, d_i, A, B, C, D$ are less than $10^9$.