This is an answer-submission problem.

Description

Teacher S is going to offer an "Origami" course next semester, and a major material needed for the class is white paper. Because the level of this course is very high, the requirements for paper dimensions are also very strict. According to the teaching plan, the course requires $n$ pieces of paper in total, where the $i$-th piece must have a length of $a_i$ and a width of $b_i$ (such a piece is referred to as an $a_i \times b_i$ piece).

Teacher S decides to produce the required pieces using the following method:

• Purchase a rectangular piece of paper of any size.
• Perform the following operations any number of times:
  • Cut an existing rectangular piece of paper horizontally or vertically into two new rectangular pieces.
  • Discard an existing rectangular piece of paper.

Finally, it must be guaranteed that exactly $n$ pieces remain, and their dimensions correspond exactly to the $n$ required pieces. Here, we consider two pieces to be identical if one can be transformed into the other by a $90^\circ$ rotation; that is, a $p \times q$ piece is the same as a $q \times p$ piece.

Teacher S hopes that the area of the initially purchased rectangular piece is as small as possible, and that one of the side lengths of the initially purchased piece falls within the range $[L, R]$. Please help him!

Input

This is an answer-submission problem with 10 input data files, named 1.in ~ 10.in.

Each input file contains only one test case.

• The first line contains three space-separated positive integers $n, L, R$.
• The next $n$ lines each contain two space-separated integers: the $i$-th line contains $a_i$ and $b_i$.

Output

For each input data file, you need to submit the corresponding output file 1.out ~ 10.out.

• The first line contains three space-separated positive integers $m, A, B$, indicating that your solution initially purchased an $A \times B$ piece and performed $m$ cutting operations.
  • You must ensure $m \leq 10^4, A \leq 10^9, B \leq 10^9$.
  • You need to satisfy $L \leq A \leq R$ or $L \leq B \leq R$ as much as possible.
  • You need to make $A \cdot B$ as small as possible.
• The next $m$ lines each represent a cutting operation. If a line contains six space-separated positive integers $p_0, q_0, p_1, q_1, p_2, q_2$, it means that this operation cuts a $p_0 \times q_0$ piece into a $p_1 \times q_1$ piece and a $p_2 \times q_2$ piece.
  • You must ensure that at least one of the following two conditions holds:
    • $p_0=p_1=p_2$ and $q_0=q_1+q_2$
    • $q_0=q_1=q_2$ and $p_0=p_1+p_2$
  • You must ensure that before performing this operation, a $p_0 \times q_0$ piece or a $q_0 \times p_0$ piece exists (whether initially purchased or generated by a previous cut); after performing this operation, the count of pieces satisfying this condition decreases by one.
  • After performing this operation, a $p_1 \times q_1$ piece and a $p_2 \times q_2$ piece are produced.
• Do not output the operations for discarding pieces.
• You must ensure that after all operations are completed, for each $i$ in the range $[1, n]$, the following process can be completed sequentially:
  • An $a_i \times b_i$ piece or a $b_i \times a_i$ piece exists, and the count of pieces satisfying this condition decreases by one.
• After outputting the above content, you are allowed to output any other content in new lines, but the total size of each output file must not exceed 1 MB. We suggest you write some meaningful content here (such as a brief description of your method) to facilitate our statistical analysis after the exam.

Subtasks

For each input file *.in, we provide a corresponding scoring file *.ans. The format of the scoring file is as follows:

• The first line is a non-negative integer $d$.
• The next 10 lines each contain an integer; let the integer on the $i$-th line be $S_i$.

Furthermore, let $S = A \cdot B$ be the area of the initially purchased piece in your solution. Scoring is performed according to the following rules:

• If your output does not meet the requirements of the [Output] section, including but not limited to too many cutting operations, an illegal operation, incomplete output, or failure to produce the required $n$ pieces, the test case receives 0 points.
• If $S \leq S_{10}$, the test case receives 10 points.
• If $S_{10} < S \leq S_9$, the test case receives 9 points.
• If $S_9 < S \leq S_8$, the test case receives 8 points.
• ...
• If $S_2 < S \leq S_1$, the test case receives 1 point.
• If $S > S_1$, the test case receives 0 points.
• If neither $L \leq A \leq R$ nor $L \leq B \leq R$ is satisfied, $d$ points are deducted from the test case, but the score will be at least 0 (it will not become negative).

We have provided all input files, scoring files, and the checker program in the paper folder in your home directory. The checker program can help you calculate the score of your output files. You can use the checker program as follows:

• Open a terminal (you can use the shortcut Ctrl+Alt+T).
• Switch to the working directory and ensure it has execution permissions:

cd ~/paper/
chmod +x checker

• For example, to score test case 1:

./checker 1

• To score all test cases:

./checker

The checker program will output relevant information on the screen in English; please read it carefully.

The checker program used during final testing will behave the same as the provided one, unless you attempt to attack the checker with an output file that does not conform to the output format.

Note

For test cases where $d=0$, although your solution will not lose points if neither side length falls within $[L, R]$, this provides a side length from a solution that can achieve full marks, which you can use for reference. You can also determine a potentially optimal side length more precisely by observing $L, R$ in the input files and $S_i$ in the scoring files.

Additionally, this formula is likely to help you solve the first test case:

$1 \times 2 \times 3 + 4 + 5 \times (6 \times (7 \times 8 + 9) + 10)$