配点 : 100 点
背景
RGB 值是通过用以下数值指定 Red(红色)、Green(绿色)、Blue(蓝色)各色来指定颜色的数值。 0 以上 255 以下的值指定颜色。
(R, G, B) = (0, 0, 128) 表示海军蓝,(255, 255, 0) 表示黄色。 另一方面,如果 (R, G, B) 全部相同,则表示白色、灰色、黑色等单色。
問題文
表示可能的颜色数量 256^3 认为较少,青叶小姐发明了每个参数取以下实数值的扩展 RGB。 0 以上 2 \times 10^5 以下实数值。
在调色板中 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 值可能会是非整数。