Задача №2519. Цирковое шоу
В цирке планируется грандиозное театрализованное шоу с участием львов и тигров. Чтобы уменьшить агрессию хищников, дрессировщики хотят составить программу таким образом, чтобы львы и тигры никогда не встречались на сцене.
Шоу состоит из \(n\) небольших представлений, в каждом из которых могут участвовать или львы, или тигры (также может случиться, что в представлении не участвуют ни те, ни другие). Представление \(i\) начинается через \(s_i\) минут от начала шоу и продолжается \(t_i\) минут. При этом в некоторые моменты времени на сцене могут идти одновременно несколько представлений (в этом случае в них не могут участвовать разные виды хищников).
Публика любит и представления со львами, и представления с тиграми. Дрессировщики просят вас помочь им распределить представления между львами и тиграми так, чтобы минимум из числа представлений с львами и числа представлений с тиграми был как можно больше.
Первая строка входного файла содержит число \(n\) (\(1 \le n \le 200\)). Следующие \(n\) строк содержат пары чисел \(s_i\), \(t_i\). (\(0 \le s_i \le 10^9\), \(1 \le t_i \le 10^9\))
Выведите в выходной файл \(n\) чисел. Число номер \(i\) должно быть равно \(1\), если в \(i\)-ом представлении участвуют львы, или \(2\), если участвуют тигры, или \(0\), если не участвуют ни те ни другие.
5 8 3 0 7 4 5 1 2 11 3 0 7 1 3 4 9 8 11 11 14
2 1 0 1 2