RGB 值通过为红、绿、蓝三种颜色分别指定 0 到 255 之间的数值来定义颜色。 例如，如果 $(R, G, B) = (0, 0, 128)$，则该颜色为海军蓝；如果 $(R, G, B) = (255, 255, 0)$，则该颜色为黄色。此外，如果 R、G 和 B 的值全部相同，则该颜色为单色，例如白色、灰色或黑色。

考虑到 $256^3$ 种可能的颜色并不足够，Aoba-san 设计了一种扩展 RGB 模型，其中每个参数可以取 0 到 $2 \times 10^5$ 之间的实数。

调色板上有 $N$ 种颜料，第 $i$ 种颜色的扩展 RGB 值为 $(r_i, g_i, b_i)$。 对于具有扩展 RGB 值 $(r, g, b)$ 的颜色，其“鲜艳度”（vividness）定义为 $(r, g, b)$ 的方差。例如，如果 $(r, g, b) = (0, 120, 480)$，则鲜艳度为 $\frac{(0-200)^2+(120-200)^2+(480-200)^2}{3} = 41600$。Aoba-san 想要通过混合调色板上的一些颜料来创造一种鲜艳的颜色。

当多种颜色同时混合时，会产生一种扩展 RGB 值为原始颜色平均值的颜色。形式上，当混合 $k$ 种扩展 RGB 值为 $(r_1, g_1, b_1), \dots, (r_k, g_k, b_k)$ 的颜色时，混合颜色的扩展 RGB 值为： $$\left( \frac{r_1+\dots+r_k}{k}, \frac{g_1+\dots+g_k}{k}, \frac{b_1+\dots+b_k}{k} \right)$$ 注意，混合后的参数值可能是非整数。

给定调色板上的 $N$ 种颜料，求通过同时混合其中恰好 $k$ 种颜料所能获得的最大鲜艳度，并将该鲜艳度对 998244353 取模后输出。 对 $k = 1, 2, \dots, N$ 分别求解上述问题。

鲜艳度对 998244353 取模的定义：

可以证明，本题中求得的鲜艳度总是一个有理数。此外，在本题的数据范围内，可以保证当所求鲜艳度表示为最简分数 $\frac{y}{x}$ 时，$x$ 不能被 998244353 整除。在这种情况下，存在唯一的 $0 \le z < 998244353$ 满足 $y \equiv xz \pmod{998244353}$，输出该 $z$ 即可。

输入格式

输入通过标准输入给出，格式如下：

$N$ $r_1 \ g_1 \ b_1$ $\vdots$ $r_N \ g_N \ b_N$

• $2 \le N \le 2 \times 10^3$
• $0 \le r_i, g_i, b_i \le 2 \times 10^5$
• 所有输入值均为整数。

输出格式

输出 $N$ 行。第 $i$ 行应包含 $k = i$ 时的答案。

样例

输入 1

3
180 0 0
0 180 180
0 0 180

输出 1

7200
5400
800

输入 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

说明

在第一个样例中，对于 $k = 2$，混合第二种和第三种颜色产生的颜色扩展 RGB 值为 $(0, 90, 180)$。该颜色的鲜艳度为 $\frac{(0-90)^2+(90-90)^2+(180-90)^2}{3} = 5400$。