Задано \(n\) отрезков \([l_i, r_i]\) для всех \(1 \le i \le n\). Ваша задача — разделить все отрезки на две непустые группы таким образом, чтобы не существовало пары отрезков из разных групп, имеющих хотя бы одну общую точку, или же сказать, что это сделать невозможно. Каждый отрезок должен принадлежать ровно одной из групп.
Чтобы оптимизировать процесс тестирования, будет дан мультитест.
Выходные данные
Для каждого запроса выведите \(n\) целых чисел \(t_1, t_2, \dots, t_n\) (\(t_i \in \{1, 2\}\)) — для каждого отрезка (в том же порядке, что и во входных данных) \(t_i\) равно \(1\), если \(i\)-й отрезок принадлежит первой группе, или же \(2\) иначе.
Если существует несколько возможных ответов, вы можете вывести любой из них. Если ответа не существует, выведите \(-1\).
Примечание
В первом запросе первый и второй отрезки должны быть в разных группах, но точный порядок чисел не важен.
Во втором запросе третий отрезок пересекается с первым и вторым отрезками, таким образом они должны находиться в одной группе, но другая группа при этом окажется пустой, поэтому ответ равен \(-1\).
В третьем запросе мы можем распределить отрезки любым образом, которые делает группы непустыми, так что любой ответ из \(6\) возможных подходит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
5 5
2 3
3
3 5
2 3
2 3
3
3 3
4 4
5 5
|
2 1
-1
1 1 2
|