الوصف

يمتد الطريق الرئيسي في ماجين (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$ أعداد صحيحة موجبة. تمثل الأعداد الصحيحة الموجبة الـ $4$ في السطر رقم $i$ القيم $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}$.