Сипаттама

Мачжэньнің басты жолы солтүстіктен оңтүстікке қарай бағытталған, ол ең оңтүстік нүктеден басталып, ең солтүстік нүктеде аяқталады. Осы жолдың бойында бүкіл жолды $n$ бөлікке бөлетін $n - 1$ жол қиылысы бар. Оңтүстіктен солтүстікке қарай санағандағы $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 = 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$ шарттарын қанағаттандыратын $a_1, a_2, \dots, a_n$ және $b_1, b_2, \dots, b_n$ табылатынына кепілдік беріледі.

Шығыс деректер

$n$ теріс емес бүтін саннан тұратын бір жол шығарыңыз. $i$-ші бүтін сан «бастапқы нүктеден $i$-ші бөлікке дейінгі жалпы күту уақыты» + «соңғы нүктеден $i$-ші бөлікке дейінгі жалпы күту уақыты» дәл $c_i$-ге тең болу ықтималдығын $998\,244\,353$ модулі бойынша білдіреді.

Мысал

1-мысал

2
25 25 25 25
0 1

499122177 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}$ болады.