Rectangle Coloring Problem

Given n axis‐parallel rectangles in the Cartesian plane, each rectangle is specified by its bottom‐left and top‐right coordinates \( (x_1,y_1) \) and \( (x_2,y_2) \) with \( x_1<x_2,\ y_1<y_2 \). It is guaranteed that no two rectangles have two edges collinear.

The boundaries of these rectangles (which consist of four line segments) may intersect with one another, thereby creating intersection points. Each rectangle’s boundary is subdivided into segments by its intersection points. In particular, if a rectangle has \( k \) intersection points on its boundary then it is partitioned into exactly \( k \) segments. (If a rectangle has no intersection point then its boundary is not colored.)

You are to color every segment on every rectangle either red or blue subject to the following conditions:

1. For any rectangle, two segments that are adjacent (i.e. share the same intersection point on that rectangle) must be colored with different colors.
2. The union of all red segments (drawn on all rectangles) forms a collection of disjoint closed curves.
3. The union of all blue segments forms a collection of disjoint closed curves.
4. Define two sets as follows:
   \( R \): Remove all blue segments, and take all points that are contained in an odd number of red closed regions.
   \( B \): Remove all red segments, and take all points that are contained in an odd number of blue closed regions.
   The coloring is legal if and only if the above conditions hold and \( R\cap B \) consists of only finitely many points.

Remark on Lexicographical Order. For any rectangle with at least one intersection point (and hence at least one segment), one may list the segments in the order in which they appear along the perimeter. We fix the order by starting from the bottom‐left corner and proceeding clockwise. A segment is represented by its color, either B (blue) or R (red). The coloring scheme for the entire instance is the concatenation of the color strings of the rectangles in the input order. The lexicographically smallest valid coloring is defined as the smallest string in dictionary order (where B is considered less than R).

Your task is to compute:

• The lexicographically smallest legal coloring scheme.
• The number of legal coloring schemes modulo \(20051131\). (Two coloring schemes are different if and only if there is at least one segment colored red in one scheme and blue in the other.)
• Note: For a rectangle with at least one intersection, the alternating condition forces the colors to alternate around its boundary. Thus, each rectangle with at least one segment has exactly 2 valid colorings (choosing whether the first segment is blue or red). For rectangles without any intersections the color is not assigned and they contribute a factor of 1.

Input Guarantee: It is guaranteed that in any legal instance every rectangle that has intersections will have an even number of intersection points on its boundary, so a legal coloring exists.

inputFormat

The first line contains an integer \( n \) (\(1\le n\le 1000\)), the number of rectangles. Each of the next \( n \) lines contains four integers \( x_1, y_1, x_2, y_2 \) (\(|x_i|,|y_i|\le 10^9\) and \( x_1<x_2,\ y_1<y_2 \)), describing a rectangle.

outputFormat

Output two lines:

• The first line is the lexicographically smallest legal coloring scheme. For a rectangle with no intersections, output nothing. For a rectangle with \( k>0 \) intersection points (which produces \( k \) segments), if the lexicographically smallest coloring is obtained by setting the first segment to B, then the rectangle’s contribution is a string of length \( k \) where the \( i\)th character is B if \( i \) is even (0-indexed) and R if \( i \) is odd.
• The second line is the number of legal coloring schemes modulo \(20051131\). Note that if a rectangle has at least one intersection, it contributes a factor of 2 (the choice of the first color), otherwise it contributes a factor of 1.

sample

1
0 0 1 1

1