Triangles

Time limit1sMemory limit128 MB

Summary
Given K points and M triangles each having the origin as one vertex, decide for each triangle whether any point lies strictly inside it, using geometric queries efficient for up to 100000 points and triangles.
Level

Hard8 of 10

Topics
Geometry, Sorting, Binary search
Solved
No attempts yet

Problem

You are given K points whose coordinates are all positive integers, and M triangles. Every triangle has one vertex at the origin (0, 0); its other two vertices have non-negative integer coordinates.

For each triangle, determine whether at least one of the K points lies strictly inside it. A point that lies on an edge or a vertex of the triangle is on the boundary and does not count as being inside.

Input

The first line contains two integers K and M.

Each of the next K lines contains two integers, the x- and y-coordinate of one point, separated by a space.

Each of the next M lines contains four integers x1 y1 x2 y2 describing one triangle: (x1, y1) and (x2, y2) are its two vertices other than the origin.

  • 1 ≤ K, M ≤ 100,000
  • 1 ≤ each coordinate of the K points ≤ 10^9
  • 0 ≤ each coordinate of a triangle vertex ≤ 10^9
  • Every triangle has a non-zero area.

Output

Print M lines. On the i-th line, print Y if at least one of the K points lies strictly inside the i-th triangle, and N otherwise.

Examples3

  1. Example 1

    Input
    4 3
1 2
1 3
5 1
5 3
1 4 3 3
2 2 4 1
4 4 6 3
    Expected output
    Y
N
Y

  2. Example 2

    Input
    1 1
2 2
5 0 0 5
    Expected output
    Y

  3. Example 3

    Input
    1 1
2 2
4 0 0 4
    Expected output
    N