M - Vivid Colors Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 100 点

背景

RGB 値とは Red (赤)、 Green (緑)、 Blue (青) の各色を 0 以上 255 以下の値で指定することで、色を指定する値です。

(R, G, B) = (0, 0, 128) であればネイビーが、(255, 255, 0) であればイエローが指定されます。 一方、(R, G, B) がすべて同じ値であれば、白、灰色、黒のようにモノクロな色が指定されます。

問題文

表現可能な色の数が 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 について解いてください。

制約

  • 2 \leq N \leq 2000
  • 0 \leq r_i, g_i, b_i \leq 2 \times 10^5 \ (1 \leq i \leq N)
  • 入力はすべて整数

部分点

  • 追加の制約 N \leq 300 を満たすデータセットに正解した場合は 30 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N
r_1 g_1 b_1
r_2 g_2 b_2
\vdots
r_N g_N b_N

出力

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

入力例 1

3
180 0 0
0 180 180
0 0 180

出力例 1

7200
5400
800

k = 2 のとき、2, 3 番目の色を混ぜることで拡張 RGB 値が (0, 90, 180) の色が生成されます。 この色の鮮やかさは \frac{(0-90)^2 + (90-90)^2 + (180-90)^2}{3} = 5400 です。

入力例 2

6
30594 32322 46262
63608 59020 98436
90150 32740 67209
82886 4627 54813
3112 67989 74995
60872 9967 9051

出力例 2

715162883
838096208
930330061
405079896
880764907
526006962

混ぜた後の色の拡張 RGB 値は非整数になることがあります。