Problem Description

Xiao C has a very large sheet of white paper (assume it is infinite). In his spare time, Xiao C likes to draw various patterns on the paper using straight lines. These lines divide the white paper into several regions. Xiao C wants to fill each region with one of two colors: black and white. If two regions share a common edge, then they are adjacent. If two adjacent regions are filled with the same color, the coloring will look very unattractive. Also, Xiao C wants to keep the center of the paper in its original white color, i.e., the region containing the origin is white.

Now Xiao C has already drawn these $n$ lines, but there are too many regions after splitting, and he cannot find a good-looking coloring plan. Xiao C hopes that you, being clever, can tell him a coloring plan. Xiao C will ask you for the colors of $m$ points on the paper to help him understand the coloring.

If the coloring plan is not unique, you only need to give one.

Input Format

The first line contains two positive integers $n, m$, representing the number of lines and the number of queried points.

The next $n$ lines each contain $4$ integers $x_1, y_1, x_2, y_2$, describing a line passing through the points $(x_1, y_1)$ and $(x_2, y_2)$.

The next $m$ lines each contain $2$ integers $q_x, q_y$, representing the color query for the point $(q_x, q_y)$.

Output Format

If no good-looking coloring plan exists, output $-1$.

If a good-looking coloring plan exists, output $m$ lines, each containing one number ($0$ or $1$), representing the color of the queried point in your coloring plan ($0$ means black, $1$ means white).

3 3
-1 -1 1 2
1 2 2 0
2 0 -1 -1
0 0
2 -1
1 3

1
0
1

Hint

Constraints and Notes on Test Cases

For $30\%$ of the test cases, $1 \le n, m \le 1000$, and each line is guaranteed to be parallel to the coordinate axes.

For $50\%$ of the test cases, $1 \le n, m \le 10^5$, and each line is guaranteed to be parallel to the coordinate axes.

For the remaining $20\%$ of the test cases, $1 \le n, m \le 1000$.

For all test cases, $1 \le n, m \le 10^5$, and $0 \le |x_i|, |y_i|, |q_x|, |q_y| \le 10^8$.

For all test cases, it is guaranteed that the point $(x_1, y_1)$ is different from the point $(x_2, y_2)$, all given lines are pairwise distinct, $(q_x, q_y)$ is not on any given line, and the origin is not on any given line.

Translated by ChatGPT 5