This is an answer-submission problem.

Description

You have organized $n$ thoughts, which are rectangles $r_i$ in your mind. You want to place them into a large rectangle $R$ in your mind, meaning you want to place $r_i$ inside $R$. To protect these thoughts, their placement positions cannot overlap with other thoughts, and their four sides must be parallel or perpendicular to the sides of $R$. Two thoughts are considered to overlap if the area of the intersection of their placement positions is greater than zero.

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

Now that I know the thoughts you have organized and have chosen the placement method for you, I want to know the best placement scheme in your mind. Please tell me.

Input

The input files nowhere1.in ~ nowhere10.in are provided in the problem directory. For each set of input data: 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, 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 $r_i$. Integers in the same line are separated by a single space.

Output

Output the answers corresponding to the input files to nowhere1.out ~ nowhere10.out. For convenience, if the side lengths of $R$ are $W, H$, we treat the placement scheme as a Cartesian coordinate system from $(0, 0)$ to $(W, H)$. Note that for test cases with type = 2, you should treat it as a $(0, 0)$ to $(W, H)$ coordinate system as per the input, not a $(0, 0)$ to $(H, W)$ coordinate system. There are $n$ lines of output, each containing one or four integers describing the placement scheme for the $i$-th thought $r_i$. The first integer in each line is $c_i$, where $c_i = 1$ means $r_i$ is placed in $R$; $c_i = 0$ means $r_i$ is not placed in $R$.

If $c_i = 1$, the line should continue with three integers $x_i, y_i, dir_i$. If $dir_i = 0$, then $r_i$ is placed in the rectangular range $(x_i, y_i) \sim (x_i + w_i, y_i + h_i)$; if $dir_i = 1$, then $r_i$ is placed in the rectangular range $(x_i, y_i) \sim (x_i + h_i, y_i + w_i)$.

Please ensure your output format is correct, and $c_i, dir_i \in \{0, 1\}$. For test cases with type = 1, all $c_i$ should be 1. Integers in the same line should be separated by a single space.

Examples

Input 1

1 3
1 1
1 1
2 1

Output 1

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

Input 2

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

Output 2

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

Subtasks

Each test case is set with 10 scoring parameters $a_1, a_2, \dots, a_{10}$. If the output is invalid, you receive zero points. Otherwise, for placement method 1, let $val$ be the area of $R$. If $val \le a_i$, you receive $i$ points. For placement method 2, let $val$ be the number of thoughts placed in $R$. If $val \ge a_i$, you receive $i$ points. If multiple scoring conditions are met, the highest score is taken.

Note

A checker tool is provided in the problem directory to verify your output file. The method to use it is to run the following in the terminal: ./checker <case_number> where <case_number> is the test data number, for example: ./checker 7 This will test whether nowhere7.out is acceptable. Please keep backups of the provided in and ans files and do not modify them arbitrarily to prevent the checker from encountering unpredictable errors.