D. Star Rail
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the far reaches of the universe, there is a special train called the Astral Express. The Astral Express, built by the renowned engineer, Aeon Akivili the Trailblazer, has the unique ability to travel throughout the galaxy using a network of star rails.

The universe is comprised of $$$n$$$ stars, which can be conceptualized as $$$n$$$ points on a 2D plane. The Astral Express begins its journey at a chosen star, referred to as the $$$i$$$-th star.

Pom-Pom, the conductor of the Astral Express, has an important task. Pom-Pom needs to draw a straight line that divides the remaining $$$n-1$$$ stars into two sets (possibly empty). This line must avoid intersecting any of the remaining $$$n-1$$$ stars, although passing through the $$$i$$$-th star is permissible. Pom-Pom will then choose one of these sets to visit, provided it contains exactly $$$k$$$ stars. If there is no set that meets this condition, Pom-Pom will not select any. The number of different sets that can be selected is denoted as $$$A_{i,k}$$$.

Pom-Pom is curious about the matrix $$$A$$$ formed by elements $$$A_{i,k}$$$. Your task is to help him determine this matrix. In other words, for each possible $$$i$$$ ($$$1 \leq i \leq n$$$) and $$$k$$$ ($$$1 \leq k \leq n-1$$$), you need to calculate the corresponding $$$A_{i,k}$$$, which represents the number of selectable sets when the Astral Express starts at the $$$i$$$-th star and the size of the set is $$$k$$$.

Input

The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \times 10^3$$$), representing the total number of stars in the universe.

Each of the next $$$n$$$ lines contains two integers $$$x_i, y_i$$$ ($$$0 \leq x_i, y_i \leq 10^9$$$), representing the coordinates of the $$$i$$$-th star in the universe. It is guaranteed that each star has a unique position.

Output

Output a matrix with $$$n$$$ rows and $$$n-1$$$ columns, representing the matrix $$$A$$$. The element at the $$$i$$$-th row and the $$$k$$$-th column should denote $$$A_{i,k}$$$, which represents the number of selectable sets when the Astral Express starts at the $$$i$$$-th star and the size of set is $$$k$$$.

Examples
Input
3
0 0
0 1
1 0
Output
2 1
2 1
2 1
Input
5
0 0
0 4
4 0
4 4
1 2
Output
4 4 4 1
4 4 4 1
3 6 3 1
3 6 3 1
4 4 4 1
Input
5
0 0
2 0
0 2
2 2
1 1
Output
3 4 3 1
3 4 3 1
3 4 3 1
3 4 3 1
4 4 4 1