Polygon Intersection Queries

You are given \(n\) points in the 2D Euclidean plane which, when connected in order, form a simple polygon. A polygon is simple if and only if all its vertices are distinct and no two non-adjacent edges intersect or touch (adjacent edges are allowed to meet exactly at their common vertex). It is guaranteed that any two consecutive edges are not collinear.

You will be given \(q\) queries. In each query, you are given two points \(P\) and \(Q\). Your task is to determine whether the line segment \(PQ\) intersects the boundary of the simple polygon. Note that if the segment passes exactly through any vertex of the polygon, it is also considered as intersecting.

inputFormat

The first line contains two integers \(n\) and \(q\) \((3 \le n \le 10^5, 1 \le q \le 10^5)\) representing the number of vertices of the polygon and the number of queries.

The next \(n\) lines each contain two integers \(x\) and \(y\) representing the coordinates of the polygon vertices given in order. The polygon is closed, i.e. an edge is considered between the last and the first vertex.

The following \(q\) lines each contain four integers \(x_1, y_1, x_2, y_2\) representing the coordinates of points \(P(x_1,y_1)\) and \(Q(x_2,y_2)\) for each query.

outputFormat

For each query, output a line containing either Yes if the segment \(PQ\) intersects the polygon boundary (or passes through a vertex), or No otherwise.

sample

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

Yes
No
Yes