Problem Background

Xiao S is a girl who loves rhythm games.

On July 7, 2077, a 3D rhythm game updated version 20.7.7, introducing a chart filled with right-angled snakes called Tnemitnep [Beyond 18+]. However, when Xiao S started playing this chart, she found that due to a game bug, all color indicators for the snakes were missing...

But as a high-level player with a ptt of 20.77 and 18 stars, Xiao S is determined to get the first theoretical score on this song. Therefore, she doesn't want to wait for the game developers to fix the bug. She decides: to calculate the original colors of all the snakes using the game's mechanics!

Unfortunately, after some simple reasoning, Xiao S found that the game's mechanics are not sufficient to uniquely determine the colors of all snakes. Therefore, Xiao S first wants to calculate a coloring possibility with the least amount of awkward hand movements using the game's "left blue right red" rule; and also calculate the number of different coloring schemes to know how many attempts she might need in the worst case to correctly catch all snakes.

Xiao S abstracts this problem into an OI problem, but she's not very good at OI, so she turns to you, who is about to participate in IOI 2024. Can you help Xiao S secure the first kill on Tnemitnep BYD while others are still confused about the red snakes and track lost?

Problem Description

Given \( n \) rectangles on a plane Cartesian coordinate system, forming several intersection points, where each rectangle's sides are parallel to the coordinate axes. Ensure that no two rectangles have sides that are collinear.

Rectangles will form several intersection points, and each rectangle is divided into several segments by these points. A segment on a rectangle is defined as the part between two adjacent intersection points on that rectangle. That is, if a rectangle has \( n \) intersection points, it is divided into \( n \) segments.

Now, each segment on every rectangle is to be colored either blue or red. The requirements are:

• Two segments belonging to the same rectangle and adjacent to the same intersection point must be of different colors;
• All red lines form several non-intersecting closed curves;
• All blue lines form several non-intersecting closed curves.

Define two figures \( R \) and \( B \):

• \( R \) is the set of points contained by an odd number of red closed curves after removing all blue lines;
• \( B \) is the set of points contained by an odd number of blue closed curves after removing all red lines.

A scheme is valid if and only if it satisfies all the above conditions and makes \( R \cap B \) contain only a finite number of points.

If you cannot understand the above definitions, refer to the sample explanation.

You need to find:

• The lexicographically smallest valid coloring scheme (lexicographical order is defined in the output format).
• The number of valid coloring schemes, modulo \( 20,051,131 \) (a prime number). 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.

Input Format

The first line contains an integer \( n \).

The next \( n \) lines, each containing 4 integers \( x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i} \), where the first two represent the bottom-left coordinates and the last two represent the top-right coordinates.

Output Format

The first line outputs the lexicographically smallest valid scheme: if there is no solution, output -1; otherwise, output a 0/1 string of length \( n \). If in your scheme, the bottom-left corner of the \( i \)-th rectangle (in input order) is red, then the \( i \)-th integer in your output should be \( 0 \); otherwise, it should be \( 1 \). It can be proven that given these numbers, the entire coloring scheme can be uniquely determined. If there are multiple solutions, your output must make the described 01 sequence lexicographically smallest.

The second line outputs the number of valid coloring schemes, modulo \( 20,051,131 \). If there is no solution, output \( 0 \).

Sample Input and Output

Input Sample #1

2
1 2 3 3
2 1 4 4

Output Sample #1

01
2

Input Sample #2

4
1 1 5 5
2 2 6 6
3 3 7 7
4 4 8 8

Output Sample #2

0000
2

Input Sample #3

2
1 1 4 4
2 2 3 3

Output Sample #3

00
2

Input Sample #4

3
1 2 4 5
2 3 5 6
3 1 6 4

Output Sample #4

-1
0

Notes

Sample explanations for samples 5, 6, and 7 can be found in the attachment.

Sample 1 Explanation:

The figure shows the given rectangles on the plane Cartesian coordinate system.

The colored parts belong to the two segments of the first rectangle.

The colored parts belong to the two segments of the second rectangle. Coloring according to the above images gives the valid scheme in the sample output:

The left scheme is invalid because the two segments of the same rectangle adjacent to the circled intersection point are the same color; the right scheme is also invalid because \( R \) and \( B \) intersect within the purple square, and \( R \cap B \) contains an infinite number of points.

The scheme is valid, 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 satisfies that the two segments of the same rectangle adjacent to any intersection point are different colors.

In the right figure, the red area marks the range of \( R \), and the blue area marks the range of \( B \). The intersection of the two figures contains only 12 points.

Sample 3 Explanation:

In this sample, because the inner part of the ring is contained by 2 red closed curves, which is an even number, the inner part does not belong to \( R \), and \( R \) forms a ring.

Data Range:

For \( 100\% \) of the data, \( 1 \leq n \leq 2 \times 10^5 \), \( x_{1,i} < x_{2,i} \), \( y_{1,i} < y_{2,i} \), \( \{x_{i,j} | 1 \leq i \leq 2, 1 \leq j \leq n\} = \{y_{i,j} | 1 \leq i \leq 2, 1 \leq j \leq n\} = \{1, 2, 3, \cdots, 2n\} \).

• Subtask 1 (5 pts): Rectangles do not intersect each other.
• Subtask 2 (20 pts): \( n \leq 13 \).
• Subtask 3 (20 pts): \( n \leq 200 \).
• Subtask 4 (25 pts): \( n \leq 2000 \).
• Subtask 5 (30 pts): No special restrictions.

见题面 Input 部分

见题面 Output 部分