配点 : 100 点
問題文
正整数 N,M 和 xy 平面上的一点是 给出了 N 。 第i 点是 (X_i,Y_i) 。然而, 3 点 (X_i,Y_i),(X_j,Y_j),(X_k,Y_k) (1 \leq i < j < k \leq N) 保证不共线。 请解决以下有关 k=1,2,\dots,N 的问题。
\{1,2,\dots,k \} 的大小是 3 的子集 对于 S= \{ s_1,s_2,\dots,s_{|S|} \} ,点集 \{ (X_{s_1},Y_{s_1}),(X_{s_2},Y_{s_2}),\dots,(X_{s_{|S|}},Y_{s_{|S|}}) \} 的凸包面积 2 次 可以证明 f(S) 。f(S) 总是一个整数,所以
\displaystyle\sum_{S \subseteq \{ 1,2,\dots,k \} ,|S| \geq 3} f(S) 的 M 求余数。
制約
- 3 \leq N \leq 1000
- 2 \leq M \leq 10^9+9
- 0 \leq X_i,Y_i \leq 10^9 (1 \leq i \leq N)
- 3 点 (X_i,Y_i),(X_j,Y_j),(X_k,Y_k) 不共线 如果正确答案是满足 (1 \leq i < j < k \leq N)
- 所有输入均为整数
部分点
- N \leq 100 的数据集,30 给予积分。
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 打印 70 给予积分。
入力
输入是按以下格式从标准输入给出的。
N M X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
i (1 \leq i \leq N) 在行中 k=i 的答案。
入力例 1
3 998244353 0 2 2 0 2 2
出力例 1
0 0 4
入力例 2
4 100 1 3 3 1 4 4 7 1
出力例 2
0 0 8 60
入力例 3
5 17 1 8 10 11 21 5 73 99 3 17
出力例 3
0 0 2 5 0