22132번 - Космическая экспедиция 스페셜 저지다국어

В 2345 году у человечества появилась возможность отправить первую космическую экспедицию к далекой планете Нутпен. Путь до нее долог и полон опасностей, поэтому было решено отправить к ней сразу n космических кораблей разных типов.

Каждый корабль может работать на одном из двух различных типов топлива. Поскольку корабли разные, их расход топлива тоже может различаться. При этом в полете корабль должен использовать только один из двух типов топлива, переходить с одного на другой в космосе нельзя.

Про корабль номер i известно, что на дорогу до планеты Нутпен он потратит или a_i килотонн топлива первого типа, или b_i килотонн топлива второго типа. В силу конструктивных особенностей кораблей, для любого из них выполняется равенство a_i + b_i = 4k, причем число k одинаково для всех кораблей.

В распоряжении командования экспедиции есть ровно k(n + 1) килотонн топлива первого типа и столько же килотонн топлива второго типа. Теперь вам необходимо решить, на каком типе топлива каждый из кораблей полетит к планете Нутпен.

Первая строка содержит одно целое число t — количество наборов входных данных в тесте. Далее следует описание самих наборов входных данных.

В первой строке описания очередного набора входных данных содержится целое число n (1 ≤ n ≤ 10⁵) — количество кораблей, которые полетят к планете Нутпен. Следующие n строк содержат по два целых неотрицательных числа a_i и b_i — количество топлива первого и второго типа, необходимое соответствующему кораблю. Гарантируется, что сумма a_i и b_i у всех кораблей одинакова, кратна четырем и не превышает 10⁸.

Сумма n во всех наборах в одном тесте не превышает 500000.

Для каждого набора входных данных выведите единственную строку, состоящую из n символов, в которой символ номер i является символом '1', если корабль номер i должен лететь на Нутпен, используя топливо первого типа, и символом '2', если ему необходимо использовать топливо второго типа. Количество необходимого топлива каждого из типов не должно превосходить k(n + 1). Если возможных ответов несколько, выведите любой из них. Гарантируется, что ответ всегда существует.