Longest Increasing Subsequence

题号：NC52920
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

Bobo is tired of all kinds of hard LIS (Longest Increasing Subsequence) problems,
so he decides to make himself some easier one.
Bobo wants to build a sequence of integers $\{x_1, x_2, \dots, x_n\}$ ,
where $x_i$ lies in the range $[a_i, b_i]$ (that is, $a_i \leq x_i \leq b_i$ ).
Let $\mathrm{LIS}(X)$ be the length of longest increasing subsequence of $\{x_1, x_2, \dots, x_n\}$ .
It's clear that $1 \leq \mathrm{LIS}(X) \leq n$ .
Bobo would like to find $g_k$ which is the number of sequences whose $\mathrm{LIS}(X) = k$ for $k = 1, 2, \dots, n$ .
Note that a sequence $\{i_1, i_2, \dots, i_k\}$ is a increasing sequence of $\{a_1, a_2, \dots, a_n\}$ only if:

$1 \leq i_1 < i_2 < \dots < i_k \leq n$
$a_{i_1} < a_{i_2} < \dots < a_{i_k}$

输入描述:

The first line contains an integer n (). 
The i-th of the following n lines contains 2 integers  ().

输出描述:

n integers .

示例1

输入

复制

2
1 2
1 2

输出

复制

3 1

示例2

输入

复制

输出

复制

0 0 1