Description

陈曦和亦遥正在玩一个游戏。在这个游戏中，二维平面上有$n$条直线。陈曦将在所有$n$的直线中首先选择恰好$k$的直线$l_1,l_2,\dots,l_k$，然后亦遥将画一条直线$L$。

亦遥的惩罚被定义为$\{l_1,l_2,\dots,l_k\}$中与$L$至少有一个交点的线条数量。请注意，两条重叠的线也有交点。

陈曦想使亦遥的惩罚最大化，而亦遥则想使其最小化。你将得到这n条线，请写一个程序来预测$k=1,2,3,\dots,n$时亦遥的惩罚，他们都以最优方案下棋。

Format

Input

第一行包含一个整数$n$，表示直线的数量。

接下来的n行包含四个整数$xa_i,ya_i,xb_i$和$yb_i$($0 \leqslant xa_i,ya_i,xb_i,yb_i \leqslant 10^9$)，表示一条直线同时经过$(xa_i,ya_i)$和$(xb_i,yb_i)$。$(xa_i,ya_i)$将永远不会与$(xb_i,yb_i)$重合。

Output

对于每个测试案例，输出$n$行，其中第$i\ (1\leqslant i \leqslant n)$包含一个整数，表示$k=i$时亦遥的惩罚。

Samples

2
1 1 2 2
0 0 2 3

0
1

3
1 1 2 2
1 1 2 2
3 2 5 4

0
0
0

Limitation

对于$40\%$的测试数据$1 \leqslant n \leqslant 1000$

对于$100\%$的测试数据$1 \leqslant n \leqslant 100000$