Опис

Головна дорога Мачженя орієнтована з півночі на південь: вона починається в найпівденнішій точці і закінчується в найпівнічнішій точці. Уздовж цієї дороги розташовано $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}$.