Have you had coffee with Kurt recently? Maybe you should.

Coffee with Kurt is very simple. $n$ of Kurt's friends tell Kurt when they're available, and Kurt schedules coffee for a single interval of time.

Kurt doesn't want to drink coffee by himself though, so he will only schedule an interval of time where, at every instant in time inside the given interval, at least $k$ of Kurt's friends will be free to drink coffee with him. Note that people are welcome to leave and join depending on their availability, Kurt just needs at least $k$ people at all points in time, otherwise he will get lonely.

For each possible value of $k$ from $1$ to $n$, help Kurt find the longest interval of time he can schedule coffee for.

Constraints

$1\le n\le {10}^5$

$1\le s_i\le t_i\le {10}^9$

Subtask 1 [1 point]

$1\le n\le 50$

Subtask 2 [1 point]

No additional constraints.

Input Specification

The first line contains a single integer, $n$.

The next $n$ lines each contain two integers, $s_i$ and $t_i$, indicating that friend $i$ is free from time $s_i$ to time $t_i$ inclusive.

Output Specification

Output $n$ integers. The $i^{\mathtt{\text{th}}}$ integer should be the maximum length of the longest interval that Kurt can schedule coffee for given he wants to get coffee with $i$ people. If it is not possible to get coffee with at least $i$ people, output $0$.

Sample Input 1

3
1 39
17 1000
1001 1002

Sample Output 1

999 22 0

Sample Explanation 1

If Kurt schedules coffee from time $1$ to time $1000$, he can get coffee with at least one friend at every point of time within. If Kurt schedules coffee from time $17$ to time $39$, he can get coffee with both the first and second friend. It is not possible for him to get coffee with all three friends simultaneously - there will not be anyone in the time range $(1000,1001)$ available for Kurt to get coffee with.