在宇宙的深处，有一列名为“星穹列车”（Astral Express）的特殊列车。星穹列车由著名的工程师阿基维利（Aeon Akivili the Trailblazer）建造，拥有通过星轨网络在银河系中穿行的独特能力。

宇宙由 $n$ 颗恒星组成，可以将其看作二维平面上的 $n$ 个点。星穹列车从选定的一颗恒星（称为第 $i$ 颗恒星）开始它的旅程。

星穹列车的列车长帕姆（Pom-Pom）有一项重要的任务。帕姆需要画一条直线，将剩下的 $n-1$ 颗恒星分成两个集合（可能为空）。这条直线必须避开剩下的 $n-1$ 颗恒星，但允许穿过第 $i$ 颗恒星。随后，如果其中一个集合恰好包含 $k$ 颗恒星，帕姆就会选择该集合进行访问。如果没有满足此条件的集合，帕姆将不会进行选择。可以被选中的不同集合的数量记为 $A_{i,k}$。

帕姆对由元素 $A_{i,k}$ 组成的矩阵 $A$ 很感兴趣。你的任务是帮助他确定这个矩阵。换句话说，对于每一个可能的 $i$ ($1 \le i \le n$) 和 $k$ ($1 \le k \le n-1$)，你需要计算对应的 $A_{i,k}$，它表示当星穹列车从第 $i$ 颗恒星出发且集合大小为 $k$ 时，可供选择的集合数量。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2 \times 10^3$)，表示宇宙中恒星的总数。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$ ($0 \le x_i, y_i \le 10^9$)，表示宇宙中第 $i$ 颗恒星的坐标。保证每颗恒星的位置都是唯一的。

输出格式

输出一个 $n$ 行 $n-1$ 列的矩阵，表示矩阵 $A$。第 $i$ 行第 $k$ 列的元素应表示 $A_{i,k}$，即当星穹列车从第 $i$ 颗恒星出发且集合大小为 $k$ 时，可供选择的集合数量。

样例

输入 1

3
0 0
0 1
1 0

输出 1

2 1
2 1
2 1

输入 2

5
0 0
0 4
4 0
4 4
1 2

输出 2

4 4 4 1
4 4 4 1
3 6 3 1
3 6 3 1
4 4 4 1

输入 3

5
0 0
2 0
0 2
2 2
1 1

输出 3

3 4 3 1
3 4 3 1
3 4 3 1
3 4 3 1
4 4 4 1