有 $n$ 桶颜料摆成一排，每桶颜料都有 $1$ 单位体积，颜色用 $(r_i, g_i, b_i)$ 表示。接下来进行 $n - 1$ 次调色：每次等概率选择当前一排中两个相邻的颜色桶，将这两桶颜料混合在一起，然后倒掉 $1$ 单位体积，于是两罐颜色分别为 $(r, g, b)$ 和 $(r', g', b')$ 的颜料混合后的颜色会变为 $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$。

如果这样随机地将颜料桶不断合并，最终得到的颜料的 $r, g, b$ 颜色值之期望是多少？

输入格式

第一行输入一个正整数 $n$，表示颜料的数量。

接下来 $n$ 行，其中第 $i$ 行三个整数 $r_i, g_i, b_i$ 表示第 $i$ 罐颜料的颜色。

输出格式

一行输出三个整数，分别为期望的 $r, g, b$ 在模 $998244353$ 意义下的取值。

即设答案中任何一个数化为最简分式后的形式为 $\frac ab$ ，其中 $a$ 和 $b$ 互质。输出整数 $x$ 使得 $bx \equiv a \pmod {998244353}$ 且 $0\le x < 998244353$。可以证明这样的整数 $x$ 是唯一的。

样例数据

样例 1 输入

3
62 12 0
12 303 0
42 192 0

样例 1 输出

42 748683417 0

样例 1 解释

如果先合并前两个，则最后混合的结果为 $\frac{\frac{x_1 + x_2}2 + x_3}2$，否则为 $\frac{x_1 + \frac{x_2 + x_3}2}2$。因而结果为 $\frac 38 x_1 + \frac 14 x_2 + \frac 38 x_3$。

因此对于 $r$ 来说，期望是 $\frac 38 \times 62 + \frac 14 \times 12 + \frac 38 \times 42 = 42$，对于 $g$ 来说，期望是 $\frac{609}4$，不难验证其在模 $998244353$ 意义下的取值是 $748683417$。

样例 2 输入

10
181 37 150
226 168 61
126 166 129
193 56 72
202 48 192
10 14 172
83 16 95
123 246 225
211 135 239
234 2 223

样例 2 输出

837029038 403008335 287595555

数据范围

对于 $100\%$ 的数据，$1\le n \le 10^5, 0\le r_i, g_i, b_i \le 255$。

故事

转眼间，兰已经成为了一位少女。她那红色的眼睛现在像火炬，正如她的性格那般，散发着青春和热情。

这时的她，喜欢在画室里挥洒她的能量。今天，她又开始随心所欲地调配颜料了。

她把 $n$ 桶颜料在她面前摆成一排，每桶颜料都有 $1$ 单位体积，颜色用 $(r_i, g_i, b_i)$ 表示。接下来她会进行 $n - 1$ 次 随心所欲的调色：每次等概率选择当前一排中两个相邻的颜色桶，将这两桶颜料混合在一起，然后倒掉 $1$ 单位体积，于是两罐颜色分别为 $(r, g, b)$ 和 $(r', g', b')$ 的颜料混合后的颜色会变为 $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$。

“你这样好浪费哦。”

“嘛……这才叫艺术不是！”

“哈，好吧好吧……”

“喂，你说，在所有可能的世界中，我期望调出的颜色……是什么样的呢？”

“你是说最终得到的颜色的 $r, g, b$ 三个值各自的期望吗？”——“哈！在问你之前我早就算出来啦！”

“哼！我，我刚刚也算出来了！”

说话的功夫，兰已经将颜色混合完了，她拿起笔刷蘸了一笔颜料，在画布上随意地画下一笔。

“喂，颜色还没混合均匀呢——”“还用你说，要的就是这个效果！”

那无数种鲜艳的色彩尚未融合，却被齐刷刷留在了画布上，那一束束细丝静静地在画布上缠绕，交融。而在笔触的末端，各种颜色相互交错晕染，就像——

那是她眼里流星的样子。

她转过身对我比了个剪刀手，“看起来还不错吧？”笑容还和孩子的时候一样灿烂。