Field Division (easy version)
Contest: Codeforces Round 950 (Div. 3)
Difficulty rating: 1900
Tags: data structures, math, sortings

This is an easy version of the problem; it differs from the hard version only by the question. The easy version only needs you to print whether some values are non-zero or not. The hard version needs you to print the exact values.

Alice and Bob are dividing the field. The field is a rectangle of size $$$n \times m$$$ ($$$2 \le n, m \le 10^9$$$), the rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$m$$$ from left to right. The cell at the intersection of row $$$r$$$ and column $$$c$$$ is denoted as ($$$r, c$$$).

Bob has $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) fountains, all of them are located in different cells of the field. Alice is responsible for dividing the field, but she must meet several conditions:

- To divide the field, Alice will start her path in any free (without a fountain) cell on the left or top side of the field and will move, each time moving to the adjacent cell down or right. Her path will end on the right or bottom side of the field.
- Alice's path will divide the field into two parts — one part will belong to Alice (this part includes the cells of her path), the other part — to Bob.
- Alice will own the part that includes the cell ($$$n, 1$$$).
- Bob will own the part that includes the cell ($$$1, m$$$).

Alice wants to divide the field in such a way as to get as many cells as possible.

Bob wants to keep ownership of all the fountains, but he can give one of them to Alice. First, output the integer $$$\alpha$$$ — the maximum possible size of Alice's plot, if Bob does not give her any fountain (i.e., all fountains will remain on Bob's plot). Then output $$$k$$$ non-negative integers $$$a_1, a_2, \dots, a_k$$$, where:

- $$$a_i=0$$$, if after Bob gives Alice the $$$i$$$-th fountain, the maximum possible size of Alice's plot does not increase (i.e., remains equal to $$$\alpha$$$);
- $$$a_i=1$$$, if after Bob gives Alice the $$$i$$$-th fountain, the maximum possible size of Alice's plot increases (i.e., becomes greater than $$$\alpha$$$).

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$2 \le n, m \le 10^9$$$, $$$2 \le k \le 2 \cdot 10^5$$$) — the field sizes and the number of fountains, respectively.

Then follow $$$k$$$ lines, each containing two numbers $$$r_i$$$ and $$$c_i$$$ ($$$1 \le r_i \le n$$$, $$$1 \le c_i \le m$$$) — the coordinates of the cell with the $$$i$$$-th fountain. It is guaranteed that all cells are distinct and none of them is ($$$n, 1$$$).

It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, first output $$$\alpha$$$ — the maximum size of the plot that can belong to Alice if Bob does not give her any of the fountains. Then output $$$k$$$ non-negative integers $$$a_1, a_2, \dots, a_k$$$, where:

- $$$a_i=0$$$, if after Bob gives Alice the $$$i$$$-th fountain, the maximum possible size of Alice's plot does not increase compared to the case when all $$$k$$$ fountains belong to Bob;
- $$$a_i=1$$$, if after Bob gives Alice the $$$i$$$-th fountain, the maximum possible size of Alice's plot increases compared to the case when all $$$k$$$ fountains belong to Bob.

If you output any other positive number instead of $$$1$$$ that fits into a 64-bit signed integer type, it will also be recognized as $$$1$$$. Thus, a solution to the hard version of this problem will also pass the tests for the easy version.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Below are the images for the second example:

The indices of the fountains are labeled in green. The cells belonging to Alice are marked in blue.

Note that if Bob gives Alice fountain $$$1$$$ or fountain $$$3$$$, then that fountain cannot be on Alice's plot.

Example input:
5
2 2 3
1 1
1 2
2 2
5 5 4
1 2
2 2
3 4
4 3
2 5 9
1 2
1 5
1 1
2 2
2 4
2 5
1 4
2 3
1 3
6 4 4
6 2
1 3
1 4
1 2
3 4 5
2 1
3 2
1 4
1 3
2 4

Example output:
1
1 0 1 
11
0 1 0 1 
1
0 0 1 1 0 0 0 0 0 
6
1 0 0 0 
1
1 1 0 0 0

Editorial:
Since Alice can only move down or to the right, if in the $$$i$$$-th row $$$x$$$ cells belong to her, then in the $$$(i-1)$$$-th row she can have no more than $$$x$$$ cells. The construction of the maximum plot can be represented as follows: we will go through the rows from bottom to top and keep track of how many cells we have collected in the row below. In the current row, we will collect either the same number of cells, or all the cells up to the leftmost fountain in the row, if there are fewer such cells.
There are three possible positions of the fountains relative to the boundary with Alice's plot:
• the fountain has no adjacent cells belonging to Alice's plot;
• the fountain has one adjacent cell belonging to Alice's plot;
• the fountain has two adjacent cells belonging to Alice's plot.
The area of Alice's plot changes only when removing the third type of fountain position, which we will call the corner. Since a corner has formed, in the row below Alice had more cells, and when removing this fountain, she will be able to take at least one cell with this fountain, and the answer for it will be $$$1$$$. For the other two types of positions, removing the fountain will not change the size of the plot, and the answer for them will be $$$0$$$ (you can proof it by yourself).
To ensure that the solution does not depend on the size of the field, we will sort the fountains in descending order of the $$$x$$$ coordinate, and in case of equality of $$$x$$$, in ascending order of the $$$y$$$ coordinate. We will iterate through the fountains in this order, keep track of the coordinates of the last corner, and update the answer when a new corner is found.