Вас попросили организовать очень важную конференцию об искусстве. Первый шаг — выбрать даты.
Конференция должна длиться некоторое число подряд идущих дней. Каждый день на конференции должен выступать один лектор, причём один и тот же лектор не может выступать более одного раза.
Вы опросили \(n\) потенциальных лекторов по поводу их доступности. Лектор \(i\) указал, что сможет выступить в любой день с \(l_i\) по \(r_i\) включительно.
Некоторый отрезок дней можно выбрать в качестве дат конференции в том случае, если существует способ на каждый из дней отрезка назначить доступного в этот день лектора, при этом назначив каждого лектора не более чем на один день.
Для каждого \(k\) от \(1\) до \(n\) найдите, сколько есть способов выбрать отрезок из \(k\) подряд идущих дней в качестве дат конференции.
Выходные данные
Выведите \(n\) целых чисел, где \(k\)-е число обозначает число способов выбрать отрезок из \(k\) подряд идущих дней в качестве дат конференции.
Примечание
В первом примере конференцию из одного дня можно устроить в любой из дней с \(1\) по \(6\). Конференцию из двух дней можно устроить с дня \(2\) по день \(3\), а также с дня \(4\) по день \(5\).
Во втором примере, несмотря на то, что сразу пятеро лекторов выразили желание выступить на конференции, все они доступны только в дни с \(1\) по \(3\), поэтому устроить конференцию длиннее трёх дней не выйдет.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
3 4
5 6
|
6
2
0
|
|
2
|
5
1 3
1 3
1 3
1 3
1 3
|
3
2
1
0
0
|