Description

NOI 2011 has started at Jilin University! To welcome the best informatics contestants from across the country, Jilin University plans to hold two grand NOI Carnival events at two different locations. Each carnival may contain many activities, and each activity can be held in only one carnival.

The organizer, Xiao An, has received $n$ applications for activities. The $i$-th activity starts at time $S_i$ and lasts for $T_i$ time. These activities can be scheduled in either carnival, or not scheduled at all.

Through extensive surveys, Xiao An found that if, at some moment, the two carnivals have activities running simultaneously (not counting the exact start and end instants), some contestants will hesitate about which carnival to go to and become unhappy. Therefore, to avoid this, Xiao An requires that there must not be two activities running at the same time in the two different carnivals (activities within the same carnival may overlap arbitrarily).

In addition, if one carnival has too few activities, its appeal will be insufficient and the scene may become dull. So Xiao An wants to arrange the schedule to maximize the number of activities in the less-populated carnival.

Furthermore, some activities are very meaningful and Xiao An hopes to hold them. He wants to know, if the $i$-th activity must be held (it can be scheduled in either of the two carnivals), what is the maximum number of activities in the less-populated carnival.

Input Format

The first line contains an integer $n$, the number of activity applications.

The next $n$ lines describe all activities. The $i$-th line contains two integers $S_i, T_i$, meaning the $i$-th activity starts at time $S_i$ and lasts for $T_i$ time.

Output Format

The first line contains an integer, the maximum number of activities in the less-populated carnival when there are no additional constraints.

Then output $n$ lines, one integer per line. The integer on the $i$-th line is the maximum number of activities in the less-populated carnival under the condition that the $i$-th activity must be chosen.

5 
8 2 
1 5 
5 3 
3 2 
5 3 

2 
2 
1 
2 
2 
2 

Hint

Sample Explanation

Without any additional constraints, an optimal arrangement is to schedule activities $1, 4$ in one carnival and activities $3, 5$ in the other carnival, leaving activity $2$ unscheduled.

For 10% of the testdata, $1 \leq n \leq 10$.

For 30% of the testdata, $1 \leq n \leq 40$.

For 100% of the testdata, $1 \leq n \leq 200$, $0 \leq S_i \leq 10^9$, $1 \leq T_i \leq 10^9$.

If the output format is incorrect (for example, fewer than $n+1$ lines), the score is $0$. If the first line of the output file is incorrect, and at least one of the last $n$ lines is also incorrect, the score is $0$. If the first line of the output file is correct, but at least one of the last $n$ lines is incorrect, the score is $4$. If the first line of the output file is incorrect, but all of the last $n$ lines are correct, the score is $6$. If all $n+1$ lines in the output file are correct, the score is $10$.

Translated by ChatGPT 5