#P18202. Vivid Colors

Vivid Colors

Vivid Colors

通常,RGB 模型分别给红、绿、蓝三个分量赋予 00 到 255255 的数值,用来表示颜色。例如,(R,G,B)=(0,0,128)(R,G,B)=(0,0,128) 表示藏青色,(255,255,0)(255,255,0) 表示黄色。当三个分量相同时,得到白色、灰色或黑色等灰度颜色。

Aoba 觉得 2563256^3 种颜色还不够,于是设计了扩展 RGB 模型,允许每个分量取 00 到 2×1052\times10^5 之间的实数。

调色板上有 NN 份颜料,第 ii 份颜料的扩展 RGB 值为 (ri,gi,bi)(r_i,g_i,b_i)。

对于扩展 RGB 值为 (r,g,b)(r,g,b) 的颜色,定义其鲜艳度为三个分量的方差。令 μ=(r+g+b)/3\mu=(r+g+b)/3,则鲜艳度为

(r−μ)2+(g−μ)2+(b−μ)23.\frac{(r-\mu)^2+(g-\mu)^2+(b-\mu)^2}{3}.

例如,(0,120,480)(0,120,480) 的三个分量平均值为 200200,鲜艳度为

$$\frac{(0-200)^2+(120-200)^2+(480-200)^2}{3}=41600.$$

将多份颜料同时混合,得到的颜色的扩展 RGB 值,是这些颜料原有 RGB 值的逐分量平均。具体地,混合 kk 份 RGB 值分别为 (r1,g1,b1),…,(rk,gk,bk)(r_1,g_1,b_1),\ldots,(r_k,g_k,b_k) 的颜料,得到

$$\left(\frac{r_1+\cdots+r_k}{k},\frac{g_1+\cdots+g_k}{k},\frac{b_1+\cdots+b_k}{k}\right).$$

混合后的分量不一定是整数。每份给定颜料至多使用一次。

对于每个 k=1,2,…,Nk=1,2,\ldots,N,求从这 NN 份颜料中选择恰好 kk 份同时混合,能够得到的最大鲜艳度,并按下述方法输出模 998244353998244353 的值。

有理数取模的定义

可以证明答案是有理数。将它写成最简分数 y/xy/x 后,题目保证 xx 不被 998244353998244353 整除。存在唯一的整数 0≤z<9982443530\le z<998244353 使

y≡xz(mod998244353),y\equiv xz\pmod{998244353},

输出这个 zz。这里先在实际有理数意义下求最大值,再对得到的答案取模。

输入格式

N
r_1 g_1 b_1
...
r_N g_N b_N

所有输入均为整数,满足:

  • 2≤N≤20002\le N\le2000;
  • 0≤ri,gi,bi≤2×1050\le r_i,g_i,b_i\le2\times10^5。

输入只有一组数据。

输出格式

输出 NN 行。第 kk 行输出混合恰好 kk 份颜料所能得到的最大鲜艳度,按上述定义模 998244353998244353。

样例 1

输入

3
180 0 0
0 180 180
0 0 180

输出

7200
5400
800

说明

当 k=2k=2 时,混合第二份和第三份颜料,得到 (0,90,180)(0,90,180),鲜艳度为

(0−90)2+(90−90)2+(180−90)23=5400.\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

输出

715162883
838096208
930330061
405079896
880764907
526006962