題目描述
麻鎮（Mazhen）嘅主幹道呈南北走向，起點位於最南端，終點位於最北端。沿住呢條道路有 $n - 1$ 個十字路口，將成條道路劃分為 $n$ 個路段。由南向北數起嘅第 $i$ 個十字路口連接住第 $i$ 個路段同埋第 $(i + 1)$ 個路段。為免方向產生歧義，第 $i$ 個十字路口同路段都定義為由南向北數起嘅第 $i$ 個十字路口同路段。
每個十字路口都設有紅綠燈。由於同十字路口相連嘅街道具有方向性，喺向北同向南行駛時，遇到相同顏色嘅燈號通過同一個十字路口所花費嘅時間可能會唔同。研究人員認為，當隨機由南向北通過第 $i$ 個十字路口時，遇到紅燈、黃燈同綠燈嘅概率分別係 $r_i, y_i, g_i$；當由北向南通過第 $i$ 個十字路口時，遇到紅燈、黃燈同綠燈嘅概率分別係 $r'_i, y'_i, g'_i$。假設到達十字路口時，一定會遇到紅燈、黃燈或者綠燈呢三種情況之一，因此 $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$。
為咗簡化問題，研究人員假設無論方向同時間點樣，當遇到紅燈、黃燈或者綠燈時，等待時間總係分別為 $1$ 秒、$2$ 秒同 $0$ 秒。
作為一名算法競賽選手，研究人員好快就計出咗喺模 $998\,244\,353$ 意義下雙向行完晒成條道路嘅期望時間。不過，而家研究人員想知一啲更加具體嘅資訊。為此，研究人員進行咗一次測試：由起點行到終點，佢記錄咗到達第 $i$ 個路段時嘅總等待時間，記為 $a_i$；然後，由終點返去起點，佢記錄咗到達第 $i$ 個路段時嘅總等待時間，記為 $b_i$。好明顯，$a_1 = b_n = 0$，而且 $a_i \le a_{i+1} \le a_i + 2$ 同埋 $b_{i+1} \le b_i \le b_{i+1} + 2$（$1 \le i < n$）。設 $c_i = a_i + b_i$。研究人員記錄咗呢次測試入面所有嘅 $c_i$（$1 \le i \le n$）。
研究人員想知呢次測試嘅實際價值，所以佢希望對每個 $i = 1, 2, \dots, n$，求出「由起點到第 $i$ 個路段嘅總等待時間」+「由終點到第 $i$ 個路段嘅總等待時間」恰好等於 $c_i$ 嘅概率，對 $998\,244\,353$ 取模。呢個問題難倒咗佢，所以佢嚟搵你幫手。
輸入格式
輸入嘅第一行包含一個整數 $n$（$2 \le n \le 2 \times 10^5$）。
接落嚟嘅 $n - 1$ 行，每行包含 $4$ 個正整數。第 $i$ 行嘅 $4$ 個正整數分別代表 $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$。保證呢 $4(n - 1)$ 個正整數都唔超過 $100$，而且 $r_i + y_i$ 同埋 $r'_i + y'_i$ 都滿足 $< 1$。
輸入嘅下一行包含 $n$ 個非負整數，其中第 $i$ 個整數代表 $c_i$（$0 \le c_i \le 2n$）。保證存在 $a_1, a_2, \dots, a_n$ 同埋 $b_1, b_2, \dots, b_n$ 滿足 $a_1 = b_n = 0$ 同埋 $a_i \le a_{i+1} \le a_i + 2$ 以及 $b_{i+1} \le b_i \le b_{i+1} + 2$（$1 \le i < n$），並且 $a_i + b_i = c_i$。
輸出格式
輸出一行，包含 $n$ 個非負整數。第 $i$ 個整數代表「由起點到第 $i$ 個路段嘅總等待時間」+「由終點到第 $i$ 個路段嘅總等待時間」恰好等於 $c_i$ 嘅概率，對 $998\,244\,353$ 取模。
範例
範例 1
2
25 25 25 25
0 1499122177 748683265備註
喺範例入面，喺兩個方向上，喺第 $1$ 個十字路口遇到紅/黃/綠燈嘅概率都係 $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$。
呢個時候，由南向北到達第 $1$ 個路段且等待時間 $a_1 = 0$ 嘅概率係 $1$（因為冇經過任何十字路口），而由北向南到達第 $1$ 個路段且等待時間 $b_1 = 0$ 嘅概率係 $\frac{1}{2}$（即係喺第 $1$ 個十字路口遇到綠燈），因此 $c_1 = 0$ 嘅概率係 $1 \times \frac{1}{2} = \frac{1}{2}$。
同樣地，由南向北到達第 $2$ 個路段且等待時間 $a_2 = 0, 1$ 嘅概率分別係 $\frac{1}{2}, \frac{1}{4}$，而由北向南到達第 $2$ 個路段且等待時間 $b_2 = 0, 1$ 嘅概率分別係 $1, 0$，因此 $c_2 = 1$ 嘅概率係 $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$。