W rzędzie ustawionych jest $n$ wiader z farbą, każde o objętości $1$ jednostki. Kolor każdego wiadra opisany jest jako $(r_i, g_i, b_i)$. Następnie wykonuje się $n - 1$ operacji mieszania: za każdym razem z jednakowym prawdopodobieństwem wybierane są dwa sąsiednie wiadra z farbą, mieszane ze sobą, a następnie odlewana jest $1$ jednostka objętości. W ten sposób, po zmieszaniu dwóch wiader o kolorach $(r, g, b)$ i $(r', g', b')$, kolor nowej mieszaniny wynosi $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$.
Jaka jest wartość oczekiwana składowych $r, g, b$ koloru końcowej farby, jeśli wiadra są łączone losowo w ten sposób?
Format wejścia
Pierwsza linia zawiera liczbę całkowitą dodatnią $n$, oznaczającą liczbę wiader z farbą.
Następnie $n$ linii, z których każda zawiera trzy liczby całkowite $r_i, g_i, b_i$, oznaczające kolor $i$-tego wiadra.
Format wyjścia
W jednej linii należy wypisać trzy liczby całkowite, będące wartościami oczekiwanymi $r, g, b$ modulo $998244353$.
Oznacza to, że jeśli wynik dla danej składowej po sprowadzeniu do ułamka nieskracalnego ma postać $\frac ab$, gdzie $a$ i $b$ są względnie pierwsze, należy wypisać taką liczbę całkowitą $x$, że $bx \equiv a \pmod {998244353}$ oraz $0\le x < 998244353$. Można dowieść, że taka liczba $x$ jest wyznaczona jednoznacznie.
Przykład
Wejście 1
3 62 12 0 12 303 0 42 192 0
Wyjście 1
42 748683417 0
Uwagi
Jeśli najpierw połączymy dwa pierwsze wiadra, końcowy wynik to $\frac{\frac{x_1 + x_2}2 + x_3}2$, w przeciwnym razie $\frac{x_1 + \frac{x_2 + x_3}2}2$. Zatem wynik to $\frac 38 x_1 + \frac 14 x_2 + \frac 38 x_3$.
Dla składowej $r$ wartość oczekiwana wynosi $\frac 38 \times 62 + \frac 14 \times 12 + \frac 38 \times 42 = 42$. Dla składowej $g$ wartość oczekiwana wynosi $\frac{609}4$, co po obliczeniu modulo $998244353$ daje $748683417$.
Wejście 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
Wyjście 2
837029038 403008335 287595555
Ograniczenia
Dla $100\%$ danych wejściowych: $1\le n \le 10^5, 0\le r_i, g_i, b_i \le 255$.
| Test | $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$ |
Historia
Lan stała się już młodą dziewczyną. Jej czerwone oczy płoną teraz jak pochodnie, odzwierciedlając jej charakter pełen młodości i entuzjazmu.
W tym czasie lubiła wyładowywać swoją energię w pracowni malarskiej. Dzisiaj znów zaczęła mieszać farby według własnego uznania.
Ustawiła przed sobą $n$ wiader z farbą w rzędzie, każde o objętości $1$ jednostki, a kolory opisane są jako $(r_i, g_i, b_i)$. Następnie wykona $n - 1$ dowolnych operacji mieszania kolorów: za każdym razem z jednakowym prawdopodobieństwem wybierze dwa sąsiednie wiadra z farbą z obecnego rzędu, zmiesza je ze sobą, a następnie odleje $1$ jednostkę objętości. W ten sposób kolor mieszaniny dwóch wiader o kolorach $(r, g, b)$ i $(r', g', b')$ stanie się $(\frac{r + r'}2, \frac{g + g'}2, \frac{b + b'}2)$.
„Marnujesz to wszystko”.
„No cóż… na tym właśnie polega sztuka!”
„Ha, niech będzie…”
„Hej, powiedz mi, jak wyglądałaby wartość oczekiwana kolorów, które mogłabym uzyskać we wszystkich możliwych światach?”
„Masz na myśli wartości oczekiwane składowych $r, g, b$ końcowej farby?” – „Ha! Zanim zapytałam, już to obliczyłam!”
„Hmph! Ja też właśnie to obliczyłam!”
W trakcie rozmowy Lan skończyła mieszać farby, wzięła pędzel, nabrała trochę farby i niedbale pociągnęła nim po płótnie.
„Hej, kolory jeszcze nie są dobrze wymieszane –” „Nie musisz mi mówić, o to właśnie chodziło!”
Niezliczone żywe kolory, jeszcze nie w pełni połączone, zostały pozostawione na płótnie. Pasma farby cicho splatały się i przenikały. A na końcach pociągnięć pędzla różne kolory mieszały się ze sobą, przypominając –
To był widok spadających gwiazd w her oczach.
Odwróciła się i pokazała mi znak zwycięstwa. „Wygląda całkiem nieźle, prawda?” Jej uśmiech był tak samo promienny, jak wtedy, gdy była dzieckiem.