有 $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$ | $=1$ |
| $2,3,4$ | $=2$ |
| $5,6$ | $=3$ |
| $7,8,9$ | $\le10$ |
| $10,11,12,13$ | $\le200$ |
| $14,15,16,17$ | $\le10^3$ |
| $18,19,20$ | $\le10^5$ |
故事
转眼间，兰已经成为了一位少女。她那红色的眼睛现在像火炬，正如她的性格那般，散发着青春和热情。
这时的她，喜欢在画室里挥洒她的能量。今天，她又开始随心所欲地调配颜料了。
她把 $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$ 三个值各自的期望吗？”——“哈！在问你之前我早就算出来啦！”
“哼！我，我刚刚也算出来了！”
说话的功夫，兰已经将颜色混合完了，她拿起笔刷蘸了一笔颜料，在画布上随意地画下一笔。
“喂，颜色还没混合均匀呢——”“还用你说，要的就是这个效果！”
那无数种鲜艳的色彩尚未融合，却被齐刷刷留在了画布上，那一束束细丝静静地在画布上缠绕，交融。而在笔触的末端，各种颜色相互交错晕染，就像——
那是她眼里流星的样子。
她转过身对我比了个剪刀手，“看起来还不错吧？”笑容还和孩子的时候一样灿烂。