F1. Разделение поля (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это упрощённая версия задачи, она отличается от усложнённой только поставленным вопросом. Простая версия требует только определить, являются ли некоторые значения ненулевыми. В сложной версии нужно определить сами значения.

Алиса и Боб делят поле. Поле представляет собой прямоугольник $$$n \times m$$$ ($$$2 \le n, m \le 10^9$$$), строки пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, столбцы пронумерованы от $$$1$$$ до $$$m$$$ слева направо. Клетка на пересечении строки $$$r$$$ и столбца $$$c$$$ обозначается как ($$$r, c$$$).

У Боба есть $$$k$$$ ($$$2 \le k \le 2 \cdot 10^5$$$) фонтанов, все из них расположены в разных клетках поля. Алиса отвечает за разделение поля, но должна соблюсти несколько условий:

  • для разделения поля Алиса начнёт свой путь в любой свободной (без фонтана) клетке на левой или верхней стороне поля и будет перемещаться, каждый раз двигаясь на соседнюю клетку вниз или вправо, свой путь она закончит на правой или нижней стороне поля;
  • этот путь Алисы разделит поле на две части — одна часть будет принадлежать Алисе (в эту часть включаются клетки её пути), другая — Бобу;
  • Алисе будет принадлежать та часть, которая включает в себя клетку ($$$n, 1$$$);
  • Бобу будет принадлежать та часть, которая включает в себя клетку ($$$1, m$$$).

Алиса хочет разделить поле так, чтобы получить как можно больше клеток.

Боб хочет сохранить владение всеми фонтанами, но один любой из них подарить Алисе. Выведите сначала целое число $$$\alpha$$$ — максимальный возможный размер участка Алисы, если Боб не подарит ей ни один фонтан (т.е. все фонтаны останутся на участке Боба). Далее выведите $$$k$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_k$$$, где:

  • $$$a_i=0$$$, если после того как Боб подарит Алисе $$$i$$$-й фонтан максимальный возможный размер участка Алисы не увеличится (т.е. останется равным $$$\alpha$$$);
  • $$$a_i=1$$$, если после того как Боб подарит Алисе $$$i$$$-й фонтан максимальный возможный размер участка Алисы увеличится (т.е. станет больше $$$\alpha$$$).
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n, m \le 10^9$$$, $$$2 \le k \le 2 \cdot 10^5$$$) — размеры поля и количество фонтанов, соответственно.

Далее следуют $$$k$$$ строк, содержащие по два числа $$$r_i$$$ и $$$c_i$$$ ($$$1 \le r_i \le n$$$, $$$1 \le c_i \le m$$$) — координаты клетки с $$$i$$$-м фонтаном. Гарантируется, что все клетки различны и среди них нет ($$$n, 1$$$).

Гарантируется, что сумма $$$k$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных сначала выведите $$$\alpha$$$ — максимальный размер участка, который может принадлежать Алисе, если Боб не подарит ей ни один из фонтанов. В следующую строку выведите $$$k$$$ неотрицательных целых чисел $$$a_1, a_2, \dots, a_k$$$, где:

  • $$$a_i=0$$$, если после того как Боб подарит Алисе $$$i$$$-й фонтан максимальный возможный размер участка Алисы не увеличится, по сравнению со случаем, когда все $$$k$$$ фонтанов принадлежат Бобу;
  • $$$a_i=1$$$, если после того как Боб подарит Алисе $$$i$$$-й фонтан максимальный возможный размер участка Алисы увеличится, по сравнению со случаем, когда все $$$k$$$ фонтанов принадлежат Бобу.

Если вместо $$$1$$$ вы выведите любое другое положительное число, которое помещается в 64-битный целочисленный знаковый тип, оно также будет распознано как $$$1$$$. Таким образом, решение усложнённой версии этой задачи также проходит тесты упрощённой.

Пример
Входные данные
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
Выходные данные
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
Примечание

Ниже приведены изображения для второго примера:

Зелёным цветом подписаны номера фонтанов. Синим цветом обозначены клетки, принадлежащие Алисе.

Обратите внимание, что если Боб дарит Алисе фонтан $$$1$$$ или фонтан $$$3$$$, то этот фонтан не может находиться на участке Алисы.