Background

In the lonely late night, the hazy moonlight puts a thin veil over everything. You walk along a quiet path, sometimes lowering your head in thought, sometimes gazing at the starry sky. You are accompanied only by loneliness and hesitation. Even if you have a few words, there is no one to talk to. Countless thoughts move with your burning heart, drifting with the wind, with nowhere to be placed.

Problem Description

You have整理 organized $n$ thoughts. In your heart, each of them is a rectangle $r_i$. You want to use a big rectangle $R$ in your heart to place them, that is, place each $r_i$ inside $R$. To protect these thoughts, their placed positions must not overlap with each other, and their four sides must be parallel or perpendicular to the sides of $R$. Two thoughts are considered overlapping if the intersection area of their placed positions is greater than zero.

You have two placing methods:

1. Place all $n$ thoughts into $R$, and hope to make the area of $R$ as small as possible.
2. Fix the size of $R$, and hope to place as many thoughts as possible into $R$.

Now I already know the thoughts you have organized, and I have chosen the placing method for you. I want to know the best placing plan in your heart. Please tell me.

Input Format

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

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

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

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

Output Format

For convenience, if the side lengths of $R$ are $W, H$, we view the placing plan as a Cartesian coordinate system $(0, 0)\sim(W, H)$. Note that for test points with $type = 2$, you should follow the input and treat it as the coordinate system $(0, 0)\sim(W, H)$, rather than $(0, 0)\sim(H, W)$.

Output a total of $n$ lines. Each line contains one or four integers, describing the placement plan of the $i$-th thought, i.e., $r_i$.

The first integer on each line is $c_i$. Here $c_i = 1$ means that $r_i$ is placed in $R$; $c_i = 0$ means that $r_i$ is not placed in $R$.

If $c_i = 1$, then output three more integers $x_i$, $y_i$, $d_{ir_i}$. If $d_{ir_i} = 0$, then $r_i$ is placed within the rectangle $(x_i, y_i)\sim(x_i + w_i, y_i + h_i)$; if $d_{ir_i} = 1$, then $r_i$ is placed within the rectangle $(x_i, y_i)\sim(x_i + h_i, y_i + w_i)$.

Please make sure your output format is correct, and that $c_i, d_{ir_i} \in \{0, 1\}$. For test points with $type = 1$, all $c_i$ must be $1$.

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

1 3
1 1
1 1
2 1

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

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

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

Hint

Scoring

Each test point provides $10$ scoring parameters $a_1, a_2, ..., a_{10}$. If a contestant’s output is invalid, the score is zero.

Otherwise, for placing method $1$, let $val$ be the area of $R$. If $val \leq a_i$, then you can get $i$ points. For placing method $2$, let $val$ be the number of thoughts placed into $R$. If $val \geq a_i$, then you can get $i$ points. If multiple scoring conditions are satisfied, the score for the test point is the highest one.

Translated by ChatGPT 5