You have been asked to organize a very important art conference. The first step is to choose the dates.

The conference must last for a certain number of consecutive days. Each day, one lecturer must perform, and the same lecturer cannot perform more than once.

You asked $n$ potential lecturers if they could participate in the conference. Lecturer $i$ indicated that they could perform on any day from $l_i$ to $r_i$ inclusive.

A certain segment of days can be chosen as the conference dates if there is a way to assign an available lecturer to each day of the segment, assigning each lecturer to no more than one day.

For each $k$ from $1$ to $n$, find how many ways there are to choose a segment of $k$ consecutive days as the conference dates.

Input

The first line of input contains one integer $n$ — the number of potential lecturers ($1 \le n \le 2 \cdot 10^5$).

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ — the segment of available days for the $i$th lecturer ($1 \le l_i \le r_i \le 2 \cdot 10^5$).

Output

Print $n$ integers, where the $k$th number denotes the number of ways to select a segment of $k$ consecutive days as conference dates.

Note

In the first testcase, a one-day conference can be organized on any of the days from $1$ to $6$. A two-day conference can be organized from day $2$ to day $3$, as well as from day $4$ to day $5$.

In the second testcase, five lecturers can perform only from day $1$ to day $3$, so it will not be possible to organize a conference longer than three days.