麻镇（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$，且对于 $1 \le i < n$，有 $a_i \le a_{i+1} \le a_i + 2$ 且 $b_{i+1} \le b_i \le b_{i+1} + 2$。令 $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 < 1$ 且 $r'_i + y'_i < 1$。

输入下一行包含 $n$ 个非负整数，其中第 $i$ 个整数表示 $c_i$（$0 \le c_i \le 2n$）。保证存在满足 $a_1 = b_n = 0$ 且对于 $1 \le i < n$ 有 $a_i \le a_{i+1} \le a_i + 2$ 且 $b_{i+1} \le b_i \le b_{i+1} + 2$，并且 $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

输出样例 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}$。