NOI2011 has begun at Jilin University! To welcome the most outstanding informatics contestants from all over the country, Jilin University has decided to host two grand NOI Carnival events at two different locations. Each carnival may include many activities, and each activity can only be held at one of the two carnivals.

The organizer of the carnival, Xiao An, has received $n$ applications for activities. The $i$-th activity has a start time $S_i$ and a duration $T_i$. These activities can be scheduled at either of the two carnival venues, or they can be left unscheduled.

Through extensive research, Xiao An discovered that if there are activities taking place at both carnival venues at the same time (excluding the exact moments when an activity starts or ends), some contestants will be conflicted about which venue to attend, leading to unhappiness. Therefore, to avoid such unpleasant situations, Xiao An requires that no two activities may be taking place simultaneously at the two different venues (activities within the same venue can be scheduled arbitrarily).

Additionally, it is easy to imagine that if a carnival venue has too few activities, it will lack appeal and may result in a lackluster atmosphere. Therefore, Xiao An hopes to make a reasonable arrangement to maximize the number of activities at the carnival that has fewer activities.

Furthermore, some activities are very meaningful, and Xiao An hopes they will be held. He wants to know, for each activity $i$, if it must be held (it can be scheduled at either of the two carnivals), what is the maximum number of activities at the carnival that has fewer activities?

Input

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

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

Output

The first line contains an integer, representing the maximum number of activities at the carnival with fewer activities under no restrictions.

The next $n$ lines each contain an integer, where the $i$-th integer represents the maximum number of activities at the carnival with fewer activities, given that activity $i$ must be selected.

Subtasks

For a test case: If the output format is incorrect (e.g., fewer than $n+1$ lines), you get 0 points. If the first line of the output file is incorrect, and at least one of the following $n$ lines is incorrect, you get 0 points. If the first line of the output file is incorrect, but all of the following $n$ lines are correct, you get 6 points. If the first line of the output file is correct, but at least one of the following $n$ lines is incorrect, you get 4 points. * If all $n+1$ lines in the output file are correct, you get 10 points.

Examples

Input 1

5
8 2
1 5
5 3
3 2
5 3

Output 1

2
2
1
2
2
2

Note

Under no restrictions, an optimal arrangement is to schedule activities 1 and 4 at one carnival, and activities 3 and 5 at the other, while activity 2 is not scheduled.

Constraints

The range and characteristics of all test data are shown in the table below: