Космическая экспедиция
시간 제한2초메모리 제한256 MB
각 함선에 두 연료 중 하나를 배정해 각 연료의 총 사용량이 k(n+1)을 넘지 않게 하라. 모든 함선은 ai+bi=4k를 만족한다.
문제
В 2345 году у человечества появилась возможность отправить первую космическую экспедицию к далекой планете Нутпен. Путь до нее долог и полон опасностей, поэтому было решено отправить к ней сразу n космических кораблей разных типов.
Каждый корабль может работать на одном из двух различных типов топлива. Поскольку корабли разные, их расход топлива тоже может различаться. При этом в полете корабль должен использовать только один из двух типов топлива, переходить с одного на другой в космосе нельзя.
Про корабль номер i известно, что на дорогу до планеты Нутпен он потратит или ai килотонн топлива первого типа, или bi килотонн топлива второго типа. В силу конструктивных особенностей кораблей, для любого из них выполняется равенство ai + bi = 4k, причем число k одинаково для всех кораблей.
В распоряжении командования экспедиции есть ровно k(n + 1) килотонн топлива первого типа и столько же килотонн топлива второго типа. Теперь вам необходимо решить, на каком типе топлива каждый из кораблей полетит к планете Нутпен.
입력
Первая строка содержит одно целое число t — количество наборов входных данных в тесте. Далее следует описание самих наборов входных данных.
В первой строке описания очередного набора входных данных содержится целое число n (1 ≤ n ≤ 105) — количество кораблей, которые полетят к планете Нутпен. Следующие n строк содержат по два целых неотрицательных числа ai и bi — количество топлива первого и второго типа, необходимое соответствующему кораблю. Гарантируется, что сумма ai и bi у всех кораблей одинакова, кратна четырем и не превышает 108.
Сумма n во всех наборах в одном тесте не превышает 500000.
출력
Для каждого набора входных данных выведите единственную строку, состоящую из n символов, в которой символ номер i является символом '1', если корабль номер i должен лететь на Нутпен, используя топливо первого типа, и символом '2', если ему необходимо использовать топливо второго типа. Количество необходимого топлива каждого из типов не должно превосходить k(n + 1). Если возможных ответов несколько, выведите любой из них. Гарантируется, что ответ всегда существует.