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 $

$ i (1 \leq i \leq N) $ 行目に $ k=i $ の答えを出力せよ。

### 部分点 - $ N \leq 100 $ を満たすデータセットに正解した場合は、 $ 30 $ 点与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 70 $ 点与えられる。 ### Constraints - $ 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) $ - 入力は全て整数