eolymp
bolt
Try our new interface for solving problems
Problems

Цирковое шоу

Цирковое шоу

Time limit 2 seconds
Memory limit 64 MiB

В цирке планируется грандиозное театрализованное шоу с участием львов и тигров. Чтобы уменьшить агрессию хищников, дрессировщики хотят составить программу таким образом, чтобы львы и тигры никогда не встречались на сцене.

Шоу состоит из n небольших представлений, в каждом из которых могут участвовать или львы, или тигры (также может случиться, что в представлении не участвуют ни те, ни другие). Представление i начинается через s_i минут от начала шоу и продолжается t_i минут. При этом в некоторые моменты времени на сцене могут идти одновременно несколько представлений (в этом случае в них не могут участвовать разные виды хищников).

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

Input data

Первая строка входного файла содержит число n (1 <= n <= 200). Следующие n строк содержат пары чисел s_i, t_i.

(0 <= s_i <= 10^9, 1 <= t_i <= 10^9)

Output data

Выведите в выходной файл n чисел. Число номер i должно быть равно 1, если в i-ом представлении участвуют львы, или 2, если участвуют тигры, или 0, если не участвуют ни те ни другие.

Examples

Input example #1
5
8 3
0 7
4 5
1 2
11 3

0 7
1 3
4 9
8 11
11 14
Output example #1
2 1 0 1 2
Author Yury Petrov, Pavel Mavrin