You are given points with positive integer coordinates. You are also given triangles, each of them having one vertex in the origin and the other vertices with non-negative integer coordinates.
You are asked to determine for each triangle whether it has at least one of the given points inside. (None of the points are on any edge of any triangle.)
输入格式
The first line will contain and .
The following lines will contain positive integers separated by one space that represent the coordinates of each point.
The next lines have non-negative integers separated by one space, and , that represent the other vertices of each triangle, except the origin.
输出格式
The output should contain exactly lines. The line should contain the character Y if the triangle (in the order of the input file) contains at least one point inside it, or N otherwise.
样例
样例
样例输入 #1
4 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3
样例输出 #1
Y
N
Y
样例输入 #2
4 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3
样例输出 #2
Y
N
Y
样例说明
数据范围与提示
In of the test cases, all triangles have vertices with coordinates and . That is, one edge of the triangle is on the x-axis, and another is on the y-axis.
In of the test cases, , , , Triangles are not degenerate (they all have nonzero area).
