As you are traveling across the vast wilderness, you come across a puzzling challenge. There is a sign that states, "Danger: River Rapids Ahead." However, you see no river in sight. Trying to prepare for this obstacle, you collect some set of stones to use to cross the river. However, since you don't know what the river ahead looks like, you want to plan out several different scenarios of "If I take this subset of stones, can I cross the river?
To know if you can successfully cross the river, you model the problem in the 2D Cartesian Plane. Each stone will be a convex polygon, and each river will be modeled as two parallel lines representing the two banks of the river. You have laid the stones out in a line and have indexed them from left to right, starting with index $$$1$$$. You have decided that for each scenario you will use each stone from $$$L$$$ to $$$R$$$, inclusive.
Since stones are heavy, you can only move them such that they are translated to another position in the coordinate plane. You cannot rotate or flip the stones. You can successfully cross the river if there are some set of translations you can apply to each stone in the range such that if you start on one bank of the river, you can walk to the other bank while staying within or on the boundary of at least one stone. Note that stones are allowed to overlap with other stones and the boundaries of the river.
The first line of input will consist of two integers $$$n$$$ and $$$r$$$ ($$$1 \leq n, r \leq 10^5$$$) — the number of stones and the number of river scenarios.
Following will be the description of each stone. Each description will start with a line consisting of a single integer $$$k_i$$$ ($$$3 \leq k_i \leq 500$$$) — the number of points that make up the stone. The following $$$k_i$$$ lines will each consist of two integers $$$x_j$$$ and $$$y_j$$$ ($$$-10^4 \leq x_j, y_j \leq 10^4$$$) - - - the $$$j$$$th point of the stone. It is guaranteed that the points form a convex polygon and the points will be given in counter clockwise order. The sum of all $$$k_i$$$ will be less than $$$5\cdot 10^5$$$. For each polygon, it is guaranteed that no three adjacent points are collinear.
The last $$$r$$$ lines will consist of 8 integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$, ($$$-2\cdot 10^9 \leq x_1, y_1, x_2, y_2 \leq 2\cdot 10^9$$$), $$$dx$$$, $$$dy$$$, ($$$-10^9 \leq dx, dy \leq 10^9, |\langle dx, dy \rangle| \gt 0$$$), $$$L$$$, and $$$R$$$ ($$$1 \leq L \leq R \leq n$$$). The first boundary of the river is the line with the direction vector $$$\langle dx, dy \rangle$$$ and that goes through point $$$(x_1, y_1)$$$. The second boundary of the river is the line with the same direction vector, but goes through point $$$(x_2, y_2)$$$. It is guaranteed that these two lines are not coincident. Lastly, the range of stones that can be used is denoted by $$$L$$$ and $$$R$$$.
For each river scenario, output "YES" if the river can be crossed with the range of stones or output "NO" if the river cannot be crossed with the range of stones. The output is case sensitive.
5 540 -11 00 1-1 03-3 -13 -10 240 0-3 0-3 -30 -381 13 14 24 43 51 50 40 230 04 04 40 0 1 15 1 0 2 50 0 1 15 1 0 1 512 12 1 3 2 -2 2 412 12 1 3 -2 2 1 55 5 7 2 -1 1 5 5
NO YES NO YES YES
