NOI Carnival Scheduling

There are n event applications. The i-th event starts at time \(S_i\) and lasts for \(T_i\) (so its ending time is \(E_i=S_i+T_i\)). These events can be assigned to either of two carnival venues, or not scheduled at all. However, events scheduled in different venues must not overlap in time (strictly speaking, they are not allowed to be "in progress" simultaneously – note that the start and end instants are not considered as being in progress). There is no restriction on overlap within the same venue.

The organizer wishes to maximize the number of events in the venue that holds fewer events. In other words, if one venue has \(a\) events and the other has \(b\) events, the goal is to maximize \(\min(a, b)\).

Furthermore, for each event \(i\) an extra query is asked: if event \(i\) must be held (it can be assigned to either venue), what is the maximum possible value of \(\min(a,b)\) achievable?

Observation: Since events in different venues must not overlap, if we let a time cut \(c\) separate the schedule, then one venue will only get events with \(E_i \le c\) (left side) and the other will only get events with \(S_i \ge c\) (right side). Note that events with \(E_i=c\) and \(S_i=c\) are allowed because the endpoints are excluded from the "in progress" time. Thus, if we define:

[ L(c)=#{\text{events with } E_i\le c}, \quad R(c)=#{\text{events with } S_i\ge c}, ]

then for any cut \(c\), we can hold at most \(\min(L(c), R(c))\) pairs (one event in each venue). Our goal is to choose a cut \(c\) to maximize \(\min(L(c), R(c))\). For a forced event, if the event is forced to the left we require \(E_i \le c\); if forced to the right we require \(S_i \ge c\). The answer for that event is the maximum possible \(\min(L(c), R(c))\) over all valid cuts \(c\) satisfying the corresponding condition. In the solution, we try both possibilities and report the best achievable value.

inputFormat

The first line contains a single integer \(n\) (the number of events). Each of the following \(n\) lines contains two integers \(S_i\) and \(T_i\) (the start time and duration of the \(i\)-th event).

outputFormat

Output \(n\) lines, where the \(i\)-th line contains a single integer: the maximum possible value of \(\min(a, b)\) achievable when event \(i\) is forced to be held.

sample

3
1 2
3 2
6 1

1
1
1