시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
В цирке планируется грандиозное театрализованное шоу с участием львов и тигров. Чтобы уменьшить агрессию хищников, дрессировщики хотят составить программу таким образом, чтобы львы и тигры никогда не встречались на сцене.
Шоу состоит из $n$ небольших представлений, в каждом из которых могут участвовать или львы, или тигры (также может случиться, что в представлении не участвуют ни те, ни другие). Представление $i$ начинается через $s_i$ минут от начала шоу и продолжается $t_i$ минут. При этом в некоторые моменты времени на сцене могут идти одновременно несколько представлений (в этом случае в них не могут участвовать разные виды хищников).
Публика любит и представления со львами, и представления с тиграми. Дрессировщики просят вас помочь им распределить представления между львами и тиграми так, чтобы минимум из числа представлений с львами и числа представлений с тиграми был как можно больше.
Первая строка входного файла содержит число $n$ ($1 \leqslant n \leqslant 200$). Следующие $n$ строк содержат пары чисел $s_i$, $t_i$. ($0 \leqslant s_i \leqslant 10^9$, $1 \leqslant t_i \leqslant 10^9$)
Выведите в выходной файл $n$ чисел. Число номер $i$ должно быть равно $1$, если в $i$-ом представлении участвуют львы, или $2$, если участвуют тигры, или $0$, если не участвуют ни те ни другие.
5 8 3 0 7 4 5 1 2 11 3
1 0 1 2 2