Given $n$ rectangles in a Cartesian coordinate system, they form several intersection points. Each rectangle's sides are parallel to the coordinate axes. It is guaranteed that no two sides of any two rectangles are collinear.

Each rectangle is divided into several segments by the intersection points lying on it. A segment of a rectangle is defined as the portion between two adjacent intersection points on that rectangle. If a rectangle has $n$ intersection points, it is divided into $n$ segments.

Now, color each segment of every rectangle either blue or red. The requirements are:

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

Define two sets $R$ and $B$:

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

A coloring scheme is valid if and only if it satisfies all the above conditions and $R \cap B$ contains only a finite number of points.

If the above definitions are unclear, please refer to the example explanations.

You need to find:

• The lexicographically smallest valid coloring scheme (the definition of lexicographical order is provided in the output format).
• The number of valid coloring schemes, modulo $20051131$ (a prime number). Two coloring schemes are different if and only if there exists at least one segment that is colored red in one scheme and blue in the other.

Input

The first line contains an integer $n$.

The next $n$ lines each contain 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

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

The second line outputs the number of valid coloring schemes, modulo $20051131$. If no solution exists, output 0.

Examples

Input 1

2
1 2 3 3
2 1 4 4

Output 1

01
2

Input 2

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

Output 2

0000
2

Input 3

2
1 1 4 4
2 2 3 3

Output 3

00
2

Input 4

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

Output 4

-1
0

Input 5

See the provided files redandblue5.in and redandblue5.ans. This example satisfies the constraints of Subtask 3.

Input 6

See the provided files redandblue6.in and redandblue6.ans. This example satisfies the constraints of Subtask 4.

Input 7

See the provided files redandblue7.in and redandblue7.ans. This example satisfies the constraints of Subtask 5.

Note

Explanation of Example 1

The figure shows the configuration of the given rectangles in the Cartesian coordinate system.

As shown, the colored parts are the two segments belonging to the first rectangle.

As shown, the colored parts are the two segments belonging to the second rectangle. Coloring according to the colors given in the images above yields the valid scheme provided in the example output:

As shown below, the left scheme is invalid because two segments belonging to the same rectangle and adjacent to the intersection point marked with a circle have the same color; the right scheme is also invalid because $R$ and $B$ intersect in the purple square shown in the figure, meaning $R \cap B$ contains infinitely many points.

The following scheme is valid, but the corresponding string 10 is not the lexicographically smallest.

Explanation of Example 2

The left figure shows all given rectangles.

The middle figure shows the corresponding coloring scheme. Each rectangle contains 6 segments, and it satisfies the condition that two segments belonging to the same rectangle and adjacent to any intersection point have 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.

Explanation of Example 3

As shown, in this example, because the interior of the loop is contained by 2 red closed curves, and 2 is an even number, the interior of the loop does not belong to $R$; thus, $R$ forms a loop.

Constraints

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}$, and $\{x_{i,j} \mid 1 \leq i \leq 2, 1 \leq j \leq n\} = \{y_{i,j} \mid 1 \leq i \leq 2, 1 \leq j \leq n\} = \{1, 2, 3, \dots, 2n\}$.

• Subtask 1 (5 pts): Rectangles do not intersect.
• 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 constraints.