AT_pakencamp_2024_day3_1_d Convex

给定正整数 $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$ 的余数。

输入通过标准输入给出，格式如下： > $N\ M\ X_1\ Y_1\ X_2\ Y_2\ \vdots\ X_N\ Y_N$

请输出 $N$ 行，其中第 $i$ 行输出 $k=i$ 时的答案。

## 部分得分 - 对于 $N \leq 100$ 的数据集，答对可得 $30$ 分。 - 对于没有额外限制的数据集，答对可得除以上 $30$ 分之外的 $70$ 分。 ## 约束条件 - $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