Kashyyyk

View as PDF

Submit solution

Points: 0.01
Time limit: 1.5s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Kashyyyk is the home planet of the Wookiees, famous for its dense forests, giant Wroshyr trees, and rich ecosystem. This planet also holds strategic importance for the Republic, which is why it has been targeted in the attack by the Separatists.

To plan the attack, the Separatists have described the surface of the planet as a ~2D~ plane, and they have identified ~n~ Wroshyr trees, with the ~i~-th tree located at integer coordinates ~p_i = (x_i, y_i)~. While the command was pondering the next step, a tactical droid realized that if the Separatists could capture the trees with indices ~i_1, i_2, \dots, i_k~, they could easily encircle the area formed by the convex hull of the points ~p_{i_1}, p_{i_2}, \dots, p_{i_k}~. Therefore, he proposed a way to calculate the importance of each Wroshyr tree as follows:

  • Randomly select a permutation ~q_1, q_2, \dots, q_n~ with values from ~1~ to ~n~.

  • Let ~s_i~ be the area of the convex hull formed by ~i~ points ~p_{q_1}, p_{q_2}, \dots, p_{q_i}~.

  • For each ~i~, the importance of tree ~q_i~ is calculated using the formula ~s_i - s_{i-1}~.

For each ~i~, let ~e_i~ be the expected value of the importance of tree ~i~. You need to find and print the value ~2 \cdot n! \cdot e_i~ (it can be proven that these values are always integers). Since these answers can be huge, you only need to print the remainder when divided by ~998244353~.

Input

Each test contains multiple test cases. The first line contains the number of test cases ~t~ (~1 \leq t \leq 10~). The description of the test cases is as follows.

The first line of the test cases contains an integer ~n~ (~1 \leq n \leq 2000~), the number of Wroshyr trees on the planet.

For the next ~n~ lines, the ~i~-th line contains two integers ~x_i, y_i~ (~0 \leq x_i, y_i \leq 10^9~), the coordinates of the ~i~-th Wroshyr tree in the ~2D~ plane.

There are no two trees at the same locations, and there are not three trees collinear.

The sum of ~n~ over all test cases does not exceed ~2000~.

Output

For each test case, print ~n~ integers, with the ~i~-th integer being ~2 \cdot n! \cdot e_i~ modulo ~998244353~.

Sample Input 1

3
3
0 0
0 4
4 4
4
0 0
0 4
4 4
4 0
4
0 0
0 4
10 10
7 0

Sample Output 1

32 32 32
192 192 192 192
444 540 876 780

Comments

Please read the guidelines before commenting.