Description

The main road of Mazhen is oriented north-south, starting at the southernmost point and ending at the northernmost point. Along this road, there are $n - 1$ intersections, dividing the entire road into $n$ segments. The $i$-th intersection from south to north connects the $i$-th segment of the road and the $(i + 1)$-th segment of the road. Due to potential ambiguity in direction, the $i$-th intersection and segment are defined as the $i$-th intersection and segment from south to north.

Each intersection has a traffic light, and due to the directional nature of the streets connected to the intersection, the time spent passing through the same intersection with the same color light can differ when going north and south. The researcher believes that when randomly passing through the $i$-th intersection from south to north, the probabilities of encountering a red light, yellow light, and green light are $r_i, y_i, g_i$, respectively; when passing through the $i$-th intersection from north to south, the probabilities of encountering a red light, yellow light, and green light are $r'_i, y'_i, g'_i$, respectively. It is assumed that upon reaching the intersection, one will encounter one of the three situations: red light, yellow light, or green light, thus $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

To simplify the problem, the researcher assumes that regardless of the direction and time, when encountering a red light, yellow light, or green light, the waiting times are always $1$ second, $2$ seconds, and $0$ seconds, respectively.

As a competitive programming participant, the researcher quickly calculated the expected time to traverse the entire road segment in both directions, under modulo $998\,244\,353$. However, now the researcher wants to know some more specific information. To this end, the researcher conducted a test: starting from the beginning to the end, he recorded the total waiting time for reaching the $i$-th segment, denoted as $a_i$; then, returning from the end to the beginning, he recorded the total waiting time for reaching the $i$-th segment, denoted as $b_i$. Clearly, $a_1 = b_n = 0$ and $a_i \le a_{i+1} \le a_i + 2$ and $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Let $c_i = a_i + b_i$. The researcher recorded all $c_i$ ($1 \le i \le n$) from this test.

The researcher wants to know the practical value of this test, so he hopes to find the probability for each $i = 1, 2, \dots, n$ that the "total waiting time from the starting point to the $i$-th segment" + "total waiting time from the end point to the $i$-th segment" is exactly equal to $c_i$, under modulo $998\,244\,353$. This has him stumped, so he comes to you for help.

Input

The first line of the input contains a single integer $n$ ($2 \le n \le 2 \times 10^5$).

The next $n - 1$ lines each contain $4$ positive integers. The $i$-th line's $4$ positive integers represent $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. It is guaranteed that these $4(n - 1)$ positive integers do not exceed $100$, and that $r_i + y_i$ and $r'_i + y'_i$ are both $< 1$.

The next line of the input contains $n$ non-negative integers, where the $i$-th integer represents $c_i$ ($0 \le c_i \le 2n$). It is guaranteed that there exist $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ satisfying $a_1 = b_n = 0$ and $a_i \le a_{i+1} \le a_i + 2$ and $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) and $a_i + b_i = c_i$.

Output

Output a line with $n$ non-negative integers. The $i$-th integer represents the probability that the "total waiting time from the starting point to the $i$-th segment" + "total waiting time from the end point to the $i$-th segment" is exactly equal to $c_i$, under modulo $998\,244\,353$.

Example

Example 1

2
25 25 25 25
0 1

499122177 748683265

Note

In the example, the probabilities of encountering red/yellow/green lights at the $1$-st intersection in both directions are $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

At this point, the probability of reaching the $1$-st segment from south to north with waiting time $a_1 = 0$ is $1$ (since no intersections were crossed), and the probability of reaching the $1$-st segment from north to south with waiting time $b_1 = 0$ is $\frac{1}{2}$ (i.e., waiting for a green light at the $1$-st intersection), thus the probability for $c_1 = 0$ is $1 \times \frac{1}{2} = \frac{1}{2}$.

Similarly, the probabilities of reaching the $2$-nd segment from south to north with waiting times $a_2 = 0, 1$ are $\frac{1}{2}, \frac{1}{4}$, and the probabilities of reaching the $2$-nd segment from north to south with waiting times $b_2 = 0, 1$ are $1, 0$, thus the probability for $c_2 = 1$ is $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.