คำอธิบาย

ถนนสายหลักของเมืองหม่าเจิ้น (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, 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}$