문제 설명

마전(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$이고 $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}$입니다.