Circus Show
A grand theatrical show featuring lions and tigers is scheduled at the circus. To minimize the aggression between the predators, the trainers aim to organize the program such that lions and tigers never appear on stage simultaneously.
The show is composed of n individual performances, each of which can feature either lions or tigers (or potentially neither). Performance i begins s_i minutes after the show starts and continues for t_i minutes. At certain times, multiple performances may overlap on stage (in such cases, different types of predators cannot be involved).
The audience enjoys both lion and tiger performances. The trainers seek your assistance in allocating the performances between lions and tigers in a way that maximizes the minimum number of performances for each.
Input
The first line of the input file contains the number n (1 <= n <= 200). The following n lines each contain a pair of numbers s_i, t_i.
(0 <= s_i <= 10^9, 1 <= t_i <= 10^9)
Output
Output n numbers to the output file. The number at position i should be 1 if lions participate in the i-th performance, 2 if tigers participate, or 0 if neither participate.