Mô tả

Trục đường chính của thị trấn Ma (Mazhen) chạy theo hướng bắc - nam, bắt đầu tại điểm cực nam và kết thúc tại điểm cực bắc. Dọc theo con đường này có $n - 1$ giao lộ, chia toàn bộ con đường thành $n$ đoạn. Giao lộ thứ $i$ tính từ nam lên bắc kết nối đoạn đường thứ $i$ và đoạn đường thứ $(i + 1)$. Để tránh sự mơ hồ về phương hướng, giao lộ và đoạn đường thứ $i$ được định nghĩa là giao lộ và đoạn đường thứ $i$ tính từ nam lên bắc.

Mỗi giao lộ đều có một đèn giao thông, và do tính chất định hướng của các con phố nối với giao lộ, thời gian đi qua cùng một giao lộ với cùng một màu đèn có thể khác nhau khi đi về phía bắc và phía nam. Nhà nghiên cứu cho rằng khi đi qua ngẫu nhiên giao lộ thứ $i$ từ nam lên bắc, xác suất gặp đèn đỏ, đèn vàng và đèn xanh lần lượt là $r_i, y_i, g_i$; khi đi qua giao lộ thứ $i$ từ bắc xuống nam, xác suất gặp đèn đỏ, đèn vàng và đèn xanh lần lượt là $r'_i, y'_i, g'_i$. Giả sử rằng khi đến giao lộ, người ta chắc chắn sẽ gặp một trong ba tình huống: đèn đỏ, đèn vàng hoặc đèn xanh, do đó $r_i + y_i + g_i = r'_i + y'_i + g'_i = 1$.

Để đơn giản hóa bài toán, nhà nghiên cứu giả định rằng bất kể hướng đi và thời điểm nào, khi gặp đèn đỏ, đèn vàng hoặc đèn xanh, thời gian chờ luôn lần lượt là $1$ giây, $2$ giây và $0$ giây.

Là một thí sinh lập trình thi đấu, nhà nghiên cứu đã nhanh chóng tính được thời gian kỳ vọng để đi hết toàn bộ đoạn đường theo cả hai chiều theo modulo $998\,244\,353$. Tuy nhiên, giờ đây nhà nghiên cứu muốn biết thêm một số thông tin cụ thể hơn. Để làm điều này, nhà nghiên cứu đã tiến hành một thử nghiệm: xuất phát từ điểm đầu đến điểm cuối, anh ghi lại tổng thời gian chờ để đến được đoạn đường thứ $i$, ký hiệu là $a_i$; sau đó, quay lại từ điểm cuối về điểm đầu, anh ghi lại tổng thời gian chờ để đến được đoạn đường thứ $i$, ký hiệu là $b_i$. Rõ ràng, $a_1 = b_n = 0$ và $a_i \le a_{i+1} \le a_i + 2$ cũng như $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$). Đặt $c_i = a_i + b_i$. Nhà nghiên cứu đã ghi lại tất cả các giá trị $c_i$ ($1 \le i \le n$) từ thử nghiệm này.

Nhà nghiên cứu muốn biết giá trị thực tiễn của thử nghiệm này, vì vậy anh hy vọng tìm được xác suất cho mỗi $i = 1, 2, \dots, n$ sao cho "tổng thời gian chờ từ điểm xuất phát đến đoạn đường thứ $i$" + "tổng thời gian chờ từ điểm kết thúc đến đoạn đường thứ $i$" đúng bằng $c_i$, theo modulo $998\,244\,353$. Điều này đã làm khó anh ấy, vì vậy anh ấy tìm đến bạn để nhờ giúp đỡ.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $n$ ($2 \le n \le 2 \times 10^5$).

$n - 1$ dòng tiếp theo, mỗi dòng chứa $4$ số nguyên dương. Ở dòng thứ $i$, $4$ số nguyên dương lần lượt biểu thị $100 \cdot r_i, 100 \cdot y_i, 100 \cdot r'_i, 100 \cdot y'_i$. Dữ liệu đảm bảo rằng $4(n - 1)$ số nguyên dương này không vượt quá $100$, và cả $r_i + y_i$ lẫn $r'_i + y'_i$ đều $< 1$.

Dòng tiếp theo của dữ liệu vào chứa $n$ số nguyên không âm, trong đó số nguyên thứ $i$ biểu thị $c_i$ ($0 \le c_i \le 2n$). Dữ liệu đảm bảo tồn tại $a_1, a_2, \dots, a_n$ và $b_1, b_2, \dots, b_n$ thỏa mãn $a_1 = b_n = 0$ và $a_i \le a_{i+1} \le a_i + 2$ cũng như $b_{i+1} \le b_i \le b_{i+1} + 2$ ($1 \le i < n$) và $a_i + b_i = c_i$.

Dữ liệu ra

In ra một dòng gồm $n$ số nguyên không âm. Số nguyên thứ $i$ biểu thị xác suất để "tổng thời gian chờ từ điểm xuất phát đến đoạn đường thứ $i$" + "tổng thời gian chờ từ điểm kết thúc đến đoạn đường thứ $i$" đúng bằng $c_i$, theo modulo $998\,244\,353$.

Ví dụ

Ví dụ 1

2
25 25 25 25
0 1

499122177 748683265

Ghi chú

Trong ví dụ, xác suất gặp đèn đỏ/vàng/xanh tại giao lộ thứ $1$ ở cả hai chiều đều là $\frac{1}{4}, \frac{1}{4}, \frac{1}{2}$.

Lúc này, xác suất đi đến đoạn đường thứ $1$ từ nam lên bắc với thời gian chờ $a_1 = 0$ là $1$ (vì không đi qua giao lộ nào), và xác suất đi đến đoạn đường thứ $1$ từ bắc xuống nam với thời gian chờ $b_1 = 0$ là $\frac{1}{2}$ (tức là gặp đèn xanh tại giao lộ thứ $1$), do đó xác suất để $c_1 = 0$ là $1 \times \frac{1}{2} = \frac{1}{2}$.

Tương tự, xác suất đi đến đoạn đường thứ $2$ từ nam lên bắc với thời gian chờ $a_2 = 0, 1$ lần lượt là $\frac{1}{2}, \frac{1}{4}$, và xác suất đi đến đoạn đường thứ $2$ từ bắc xuống nam với thời gian chờ $b_2 = 0, 1$ lần lượt là $1, 0$, do đó xác suất để $c_2 = 1$ là $1 \times \frac{1}{4} + 0 \times \frac{1}{2} = \frac{1}{4}$.