У цирку планується грандіозне театралізоване шоу за участю левів та тигрів. Щоб зменшити агресію хижаків, дресирувальники хочуть скласти програму таким чином, щоб леви та тигри ніколи не зустрічалися на сцені.

Шоу складається з \(𝑛\) невеликих вистав, у кожному з яких можуть брати участь або леви, або тигри (також може статися, що у виставі не беруть участь ні ті, ні інші). Вистава \(𝑖\) починається через \(𝑠_𝑖\) хвилин від початку шоу і триває \(𝑡_𝑖\) хвилин. При цьому в деякі моменти часу на сцені можуть йти одночасно кілька вистав (у цьому випадку в них не можуть брати участь різні види хижаків). Публіка любить і вистави з левами, і вистави з тиграми.

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

Формат вхідних даних

Перший рядок містить число \(𝑛\) (\(1≤𝑛≤200\)).

Наступні \(n\) рядків містять пари чисел \(𝑠_𝑖\), \(𝑡_𝑖\). (\(0≤𝑠_𝑖≤10^9\) , \(1≤𝑡_𝑖≤10^9\) )

Формат вихідних даних

Виведіть \(𝑛\) чисел.

Число номер \(𝑖\) повинне бути рівним 1 , якщо в \(𝑖\) - й виставі беруть участь леви, або 2 , якщо беруть участь тигри, або 0, якщо не беруть участь ні ті, ні інші.

Приклад вхідних даних

5
8 3
0 7
4 5
1 2
11 3

Приклад вихідних даних

2 1 0 1 2