Циркове шоу
В цирку планується грандіозне театралізоване шоу з участю левів та тигрів. Щоб зменшити агресію хижаків, дресувальники хочуть скласти програму таким чином, щоб леви і тигри ніколи не зустрічались на сцені.
Шоу складається з n невеликих вистав, у кожній з яких можуть приймати участь або леви, або тигри (також може статись, що у виставі не приймають участь ні ті, ні інші). Вистава i починається через s_i хвилин від початку шоу і продовжується t_i хвили. При цьому у деякі моменти часу на сцені можут йти одночасно декілька вистав (у цьому випадку в них не можуть приймати участь різні види хижаків).
Публіка любить і вистави з левами, і вистави з тиграми. Дресувальники просять вас допомогти їм розподілити вистави між левами і тиграми так, щтоб мінімум з числа вистав з левами і числа вистав з тиграми був якомога більшим.
Вхідні дані
Перший рядок вхідного файлу містить число n (1 <= n <= 200). Наступні n рядків містять пари чисел s_i, t_i.
(0 <= s_i <= 10^9, 1 <= t_i <= 10^9)
Вихідні дані
Виведіть у вихідний файл n чисел. Число номер i повинно бути рівним 1, якщо у i-й виставі приймають участь леви, або 2, якщо приймають участь тигри, або 0, якщо не приймають участь ні одні ні другі.