There are $n$ buckets of paint arranged in a row, each with a volume of $1$ unit, with colors represented by $(r_i, g_i, b_i)$. The following $n - 1$ mixing operations are performed: in each step, two adjacent buckets of paint are chosen with equal probability, mixed together, and then $1$ unit of volume is discarded. Thus, two paints with colors $(r, g, b)$ and $(r', g', b')$ result in a new color of $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$.
If the paint buckets are merged randomly in this manner, what is the expected value of the $r, g, b$ color components of the final paint?
Input
The first line contains a positive integer $n$, representing the number of paint buckets.
The next $n$ lines each contain three integers $r_i, g_i, b_i$, representing the color of the $i$-th bucket.
Output
Output three integers on a single line, representing the expected values of $r, g, b$ modulo $998244353$.
Specifically, if the answer for any component is expressed as an irreducible fraction $\frac ab$, where $a$ and $b$ are coprime, output an integer $x$ such that $bx \equiv a \pmod {998244353}$ and $0\le x < 998244353$. It can be proven that such an integer $x$ is unique.
Examples
Input 1
3 62 12 0 12 303 0 42 192 0
Output 1
42 748683417 0
Note 1
If the first two are merged first, the final result is $\frac{\frac{x_1 + x_2}2 + x_3}2$; otherwise, it is $\frac{x_1 + \frac{x_2 + x_3}2}2$. Therefore, the result is $\frac 38 x_1 + \frac 14 x_2 + \frac 38 x_3$.
Thus, for $r$, the expectation is $\frac 38 \times 62 + \frac 14 \times 12 + \frac 38 \times 42 = 42$. For $g$, the expectation is $\frac{609}4$, and it is easy to verify that its value modulo $998244353$ is $748683417$.
Input 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
Output 2
837029038 403008335 287595555
Constraints
For $100\%$ of the data, $1\le n \le 10^5, 0\le r_i, g_i, b_i \le 255$.
| Test Case | $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$ |
Note
In the blink of an eye, Lan has become a young girl. Her red eyes are now like torches, radiating youth and passion, just like her personality.
At this moment, she loves to unleash her energy in the art studio. Today, she has started mixing paints as she pleases.
She places $n$ buckets of paint in a row in front of her, each with a volume of $1$ unit, with colors represented by $(r_i, g_i, b_i)$. Next, she will perform $n - 1$ arbitrary mixing operations: each time, she chooses two adjacent buckets of paint in the current row with equal probability, mixes them together, and then discards $1$ unit of volume. Thus, two paints with colors $(r, g, b)$ and $(r', g', b')$ result in a new color of $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$.
"You're being so wasteful."
"Well... that's what art is all about!"
"Ha, alright, alright..."
"Hey, tell me, in all possible worlds, what is the expected color I will mix..."
"Do you mean the expected values of the $r, g, b$ components of the final color?" — "Ha! I already calculated that before asking you!"
"Hmph! I, I just calculated it too!"
While speaking, Lan had already finished mixing the paints. She picked up a brush, dipped it into the paint, and made a random stroke on the canvas.
"Hey, the colors aren't mixed evenly yet—" "You don't have to tell me, that's the effect I wanted!"
Those countless vibrant colors, not yet fully blended, were left on the canvas in streaks. Those thin strands quietly intertwined and merged on the canvas. And at the end of the brushstrokes, various colors were interlaced and smudged, just like—
That was the look of meteors in her eyes.
She turned around and made a peace sign at me, "Looks pretty good, right?" Her smile was as bright as when she was a child.