Problem Background

In the silent midnight, the朦朦胧胧的moonlight envelops everything in a thin veil. You stroll along the secluded path, sometimes deep in thought, sometimes gazing at the starry sky, accompanied only by solitude and wander. Even a single word is unheard, and no one to confide in. Countless thoughts, along with your fervent heart, drift with the wind, restless and unanchored...

Problem Description

You have sorted out $n$ thoughts, each represented as a rectangle $r_i$ in your mind. You wish to place them within a larger rectangle $R$ in your heart, meaning to position $r_i$ inside $R$. To protect these thoughts, their placements must not overlap with each other, and their sides must be parallel or perpendicular to the sides of $R$. Two thoughts overlap if their overlapping area is greater than zero.

You have two placement methods:
1. Place all $n$ thoughts within $R$, aiming to minimize the area of $R$.
2. Fix the size of $R$, aiming to place as many thoughts as possible within $R$.

Now that I know your sorted thoughts and have chosen the placement method for you, I want to know your best placement plan. Please tell me.

Input Format

The first line contains two integers $type$ and $n$, representing the placement method and the number of thoughts, respectively.

If $type = 2$, the second line contains two integers $W$ and $H$, representing the dimensions of $R$.

The next $n$ lines each contain two integers $w_i$ and $h_i$, representing the dimensions of the $i$-th thought $r_i$.

Integers in the same line are separated by a single space.

Output Format

For convenience, if the dimensions of $R$ are $W$ and $H$, we consider the placement scheme as a Cartesian coordinate system from $(0, 0)$ to $(W, H)$. Note that for test cases where $type = 2$, you should consider it as a coordinate system from $(0, 0)$ to $(W, H)$ as per the input, not from $(0, 0)$ to $(H, W)$.

The output consists of $n$ lines, each describing the placement of the $i$-th thought $r_i$.

Each line starts with an integer $c_i$, where $c_i = 1$ indicates that $r_i$ is placed within $R$; $c_i = 0$ indicates that $r_i$ is not placed within $R$.

If $c_i = 1$, the line should then output three integers $x_i$, $y_i$, and $d_{ir_i}$. If $d_{ir_i} = 0$, $r_i$ is placed in the rectangle from $(x_i, y_i)$ to $(x_i + w_i, y_i + h_i)$; if $d_{ir_i} = 1$, $r_i$ is placed in the rectangle from $(x_i, y_i)$ to $(x_i + h_i, y_i + w_i)$.

Ensure that your output format is correct, and that $c_i, d_{ir_i} \in \{0, 1\}$. For test cases where $type = 1$, all $c_i$ should be $1$.

Integers in the same line should be separated by a single space.

Sample Input and Output

Sample Input #1

1 3
1 1
1 1
2 1

Sample Output #1

1 0 0 0
1 0 1 0
1 1 0 1

Sample Input #2

2 4
2 2
1 1
1 1
2 1
2 1

Sample Output #2

1 0 0 0
1 0 1 0
1 1 0 1
0

Notes

Scoring Method

Each test point has 10 scoring parameters $a_1, a_2, ..., a_{10}$. If the player's output is invalid, they receive zero points.

Otherwise, for placement method 1, let $val$ be the area of $R$. If $\leq a_i$, you earn $i$ points; for placement method 2, let $val$ be the number of thoughts placed within $R$. If $\geq a_i$, you earn $i$ points. The highest score among the satisfied conditions is taken for the test point.

见题面 Input 部分

见题面 Output 部分