Всего поровну

Двумерная таблица состоит из S строк и S столбцов. Часть её клеток заштрихованы, и в них больше ничего нельзя записать. Свободными остались N клеток.

В них необходимо расставить нули и единицы так, чтобы:

в каждой строке количество нулей и количество единиц различалось бы не более чем на 1;

в каждом столбце количество нулей и количество единиц также различалось бы не более чем на 1.

Таким образом, вам надо заполнить оставшиеся N клеток с выполнением указанных правил.

Каждая клетка таблицы определяется двумя числами от 1 до S — номером строки и номером столбца. Свободная клетка номер i расположена в ai-й строке и в столбце номер bi. Числа ai и bi могут принимать любые значения от 1 до S. В частности, может оказаться так, что в какой-нибудь строке не будет ни одной свободной клетки.

Формат входных данных
Сначала вводятся два целых числа S и N (1⩽S⩽100000, 1⩽N⩽min(100000,S2)). Далее расположены N пар натуральных чисел (ai,bi), не превосходящих S. Гарантируется, что все описанные таким образом свободные клетки различные.

Формат выходных данных
Если искомого способа не существует, выведите слово Impossible. Иначе выведите единственную строку из N символов ‘0’ и ‘1’. Символ на i-й позиции соответствует значению i-й клетки в той же нумерации, в которой они были перечислены во входных данных.

0