Bobo 厌倦了各种困难的 LIS（最长上升子序列）问题，因此他决定给自己出一些简单的题目。

Bobo 想要构造一个整数序列 $\{x_1, x_2, \dots, x_n\}$，其中 $x_i$ 位于区间 $[a_i, b_i]$ 内（即 $a_i \le x_i \le b_i$）。

令 $\text{LIS}(X)$ 为序列 $\{x_1, x_2, \dots, x_n\}$ 的最长上升子序列的长度。显然 $1 \le \text{LIS}(X) \le n$。Bobo 想要对于 $k = 1, 2, \dots, n$，求出满足 $\text{LIS}(X) = k$ 的序列个数 $g_k$。

注意，序列 $\{i_1, i_2, \dots, i_k\}$ 是 $\{a_1, a_2, \dots, a_n\}$ 的上升子序列，当且仅当：

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

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5$)。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i \le b_i \le 10^3$)。

输出格式

输出 $n$ 个整数 $g_1, g_2, \dots, g_n$。

样例

样例输入 1

2
1 2
1 2

样例输出 1

3 1

样例输入 2

3
1 1
2 2
3 3

样例输出 2

0 0 1