תיאור

הכביש הראשי של מאז'ן (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}$.