AT_tupc2023_m Vivid Colors

表現可能な色の数が $ 256^3 $ では少ないと考えたあおばさんは、各パラメータが $ 0 $ 以上 $ 2 \times 10^5 $ 以下の実数値をとるような拡張 RGB を考案しました。 パレットに $ N $ 個の絵の具があり、 $ i $ 番目の色の拡張 RGB 値は (R, G, B) の順に $ (r_i, g_i, b_i) $ です。 拡張 RGB 値が $ (r, g, b) $ である色に対し、その色の**鮮やかさ**を $ (r, g, b) $ の分散によって定義します。 たとえば $ (r, g, b) = (0, 120, 480) $ で表される色の鮮やかさは $ \frac{(0 - 200)^2 + (120 - 200)^2 + (480 - 200)^2}{3} = 41600 $ です。 あおばさんはパレットにある色のいくつかを混ぜることで鮮やかな色を作りたいと考えています。 複数の色を同時に混ぜると、拡張 RGB 値の各パラメータがもとの色の平均であるような色が生成されます。 混色後のパラメータの値は非整数になりうることに注意してください。 パレットにある $ N $ 個の絵の具の中から**ちょうど** $ k $ 個を選び、それらを同時に混ぜるとき、 混ぜた後の色の鮮やかさとしてありうる最大値を $ \bmod{998244353} $ で求めてください。 有理数 $ \bmod{998244353} $ の定義 この問題で求める値は有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 $ \frac{y}{x} $ で表した時に $ x $ が $ 998244353 $ で割り切れないことが保証されます。 このとき $ xz \equiv y \pmod{998244353} $ を満たすような $ 0 $ 以上 $ 998244352 $ 以下の整数 $ z $ が一意に定まります。この $ z $ を答えてください。 以上の問題を $ k = 1, 2, \ldots, N $ について解いてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ r_1 $ $ g_1 $ $ b_1 $ $ r_2 $ $ g_2 $ $ b_2 $ $ \vdots $ $ r_N $ $ g_N $ $ b_N $

$ i $ 行目には $ k = i $ の答えを出力せよ。

### 背景 RGB 値とは Red (赤)、 Green (緑)、 Blue (青) の各色を $ 0 $ 以上 $ 255 $ 以下の値で指定することで、色を指定する値です。 (R, G, B) $ = (0, 0, 128) $ であればネイビーが、 $ (255, 255, 0) $ であればイエローが指定されます。 一方、(R, G, B) がすべて同じ値であれば、白、灰色、黒のようにモノクロな色が指定されます。 ### 部分点 - 追加の制約 $ N \leq 300 $ を満たすデータセットに正解した場合は $ 30 $ 点が与えられる。 ### Sample Explanation 1 $ k = 2 $ のとき、 $ 2, 3 $ 番目の色を混ぜることで拡張 RGB 値が $ (0, 90, 180) $ の色が生成されます。 この色の鮮やかさは $ \frac{(0-90)^2 + (90-90)^2 + (180-90)^2}{3} = 5400 $ です。 ### Sample Explanation 2 混ぜた後の色の拡張 RGB 値は非整数になることがあります。 ### Constraints - $ 2 \leq N \leq 2000 $ - $ 0 \leq r_i, g_i, b_i \leq 2 \times 10^5 \ (1 \leq i \leq N) $ - 入力はすべて整数