P10015 [CTT Mutual Test 2023] Left Blue, Right Red

Xiao S is a girl who likes rhythm games. On July 7, 2077, a certain 3D rhythm game updated to version 20.7.7 and released a chart full of right-angle snakes: Tnemitnep [Beyond 18+]. But when Xiao S started playing this chart, she found that because of a game bug, all color indicators of the snakes were gone... However, as a top-tier 18-star player with ptt 20.77, Xiao S is determined to get the first theoretical max position on this song, so she does not want to wait for the developers to fix the bug. She decided to compute the original colors of all snakes by using the game mechanics! Unfortunately, after some simple reasoning, Xiao S found that the mechanics are not enough to uniquely determine the colors of all snakes. Therefore, Xiao S first hopes to compute, under the game rule “left blue, right red”, a coloring possibility that uses as few “cross-hand” (fǎnshǒu, i.e. switching hands) as possible; meanwhile, she also wants to compute the number of different coloring schemes, to know how many attempts she may need in the worst case to catch all snakes correctly. Xiao S abstracted this problem into an OI problem, but she is not very good at OI, so she came to you, who are about to participate in IOI 2024. Can you help Xiao S get the first clear of Tnemitnep BYD while others are still confusedly getting Track Lost on red snakes?

Given $n$ rectangles on the 2D Cartesian plane, they form several intersection points. All edges of each rectangle are parallel to the coordinate axes. **It is guaranteed that no two edges (from any rectangles) are collinear.** Rectangles form several intersection points, and each rectangle is divided into several segments by the intersection points on it. Define a **segment** on a rectangle as the part of that rectangle between two adjacent intersection points. That is, if a rectangle has $n$ intersection points on it, then it is divided into $n$ segments. Now color every segment on every rectangle either blue or red, such that: - For any intersection point, the two segments **adjacent to it and belonging to the same rectangle** have different colors. - All red segments form several pairwise disjoint closed curves. - All blue segments form several pairwise disjoint closed curves. Define two shapes $R,B$: - $R$ is the set of all points that are contained in an **odd** number of red closed curves, after deleting all blue segments. - $B$ is the set of all points that are contained in an **odd** number of blue closed curves, after deleting all red segments. A scheme is legal if and only if it satisfies all conditions above, and **makes $R\cap B$ contain only finitely many points**. **If you cannot understand the definitions above, please refer to the sample explanations.** You need to compute: - The lexicographically smallest legal coloring scheme (the lexicographic order is defined in the Output Format). - The number of legal coloring schemes modulo $20,051,131$ (a prime). Two coloring schemes are different if and only if there exists a segment that is colored red in one scheme and blue in the other.

The first line contains an integer $n$. The next $n$ lines: the $i$-th line contains four integers $x_{1,i},y_{1,i},x_{2,i},y_{2,i}$, where the first two are the bottom-left corner coordinates, and the last two are the top-right corner coordinates.

On the first line, output the lexicographically smallest legal scheme: if there is no solution, output a single line `-1`; otherwise output a 0/1 string of length $n$. In your scheme, if the bottom-left corner of the $i$-th rectangle in input order is red, then the $i$-th character should be `0`; otherwise it should be `1`. It can be proven that after these values are given, the entire coloring scheme is uniquely determined. If there are multiple solutions, the solution you output must make the **01 string described above lexicographically smallest**. On the second line, output the number of legal coloring schemes modulo $20,051,131$. If there is no solution, output $0$.

Samples 5, 6, and 7 are in the attachments. --- Sample 1 explanation:  The figure above shows the given rectangles on the 2D Cartesian plane.  In the figure above, the colored parts are two segments belonging to rectangle 1.  In the figure above, the colored parts are two segments belonging to rectangle 2. Coloring according to the colors in the figures above yields the legal scheme shown in the sample output:  In the figure below, the left scheme is illegal because the two segments adjacent to the circled intersection point and belonging to the same rectangle have the same color. The right scheme is also illegal because $R$ and $B$ intersect inside the purple square in the figure, so $R\cap B$ contains infinitely many points.  The scheme below is legal, but the corresponding string `10` is not lexicographically smallest.  --- Sample 2 explanation:  The left figure shows all given rectangles. The middle figure shows the corresponding coloring scheme. Each rectangle contains $6$ segments, and it satisfies that for any intersection point, the two adjacent segments belonging to the same rectangle have different colors. In the right figures, the red region marks the range of $R$, and the blue region marks the range of $B$. The intersection of the two shapes contains only $12$ points. --- Sample 3 explanation:  As shown, in this sample, the inside part of the ring is contained in $2$ red closed curves. Since $2$ is even, the inside of the ring does not belong to $R$, and $R$ forms a ring. --- Constraints: For $100\%$ of the data, it is guaranteed that $1\leq n\leq 2\times 10^5$, $x_{1,i}