Description

You are asked to hold a conference, the first step of which is to choose the proper dates. The conference must span several consecutive days. Each day, one lecturer is needed to give a presentation, and each lecturer cannot give more than one presentation during the conference. There are $n$ lecturers that can participate in the conference in total, the ith of whom is available from day $l_i$ to day $r_i$, inclusive of $l_i$ and $r_i$. Several consecutive days can be chosen to hold the conference if there is a way to invite available lecturers to each of the days, without inviting lecturers more than once. For $k$ from $1$ to $n$, we want to find out how many ways are there to choose $k$ consecutive days as the conference dates.

Format

Input

The first line of input contains one integer n, indicating the number of lecturers ($1 \leq n \leq 1 \times 10^4$). Each of the next n lines contains two integers $l_i$ and $r_i$, the $i_{th}$ lecturer is available during these days ($1 \leq li \leq ri \leq 2 × 10^4$).

Output

Print $n$ lines, the $k_{th}$ line contains one integer indicating the number of ways of selecting a conference of $k$ days.

Samples

3
1 3
2 4
3 6

6
4
3

Explanation

k = 1: all the days are valid, so there are 6 ways. k = 2: [1, 2], [2, 3], [3, 4], [4, 5] are valid, [5, 6] is not valid, so there are 4 ways. k = 3: [1, 3], [2, 4], [3, 5] are valid, 3 ways.

5
1 3
1 3
1 3
1 3
1 3

3
2
1
0
0

Explanation

k = 1: all the days are valid, so there are 6 ways. k = 2: [1, 2], [2, 3], [3, 4], [4, 5] are valid, [5, 6] is not valid, so there are 4 ways. k = 3: [1, 3], [2, 4], [3, 5] are valid, 3 ways.

Limitation

1s, 256MB for test cases with $n < 100$ 10s, 4096MB for the others