Описание

Главная дорога Мачжэня ориентирована с севера на юг: она начинается в самой южной точке и заканчивается в самой северной точке. Вдоль этой дороги расположено $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 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}$.