Acmicpc/uva11040/bricks

ต้นฉบับ: uva onlinejudge ข้อ 11040

11040 - Add bricks in the wall

Time limit: 3 วินาที

นี่ไม่ใช่ ``another brick in the wall", แต่เป็นการใส่เลขลงในกำแพงเท่านั้น สมมติว่าคุณมีกำแพงเป็นรูปสามเหลี่ยม ดังตัวอย่างที่แสดงด้านล่าง (ดูรูปจากโจทย์ต้นฉบับ [1]) กำแพงนี้มี 9 แถว แถวที่ i จะมีก้อนหิน i ก้อนพอดี เราจะเรียกแถวบนสุว่าแถวที่หนึ่งและแถวล่างสุดว่าแถวที่เก้า

หินบางก้อนจะมีตัวเลขระบุเอาไว้ และบางก้อนจะเป็นหินว่าง ๆ สังเกตว่าหินที่มีเลขระบุจะอยู่ในแถวที่เป็นเลขคี่ นอกจากนั้นยังอยู่ในตำแหน่งที่เป็นเลขคี่ในแถวนั้นด้วยเช่นกัน

ปัญหาที่คุณจะต้องแก้ก็คือ ให้คุณหาตัวเลขมาใส่ในก้อนหินที่เหลือ โดยรับประกันว่าจะต้องเป็นไปตามกฎที่ระบุว่าจำนวนบนก้อนหินก้อนใด ๆ จะต้องเท่ากับผลรวมของจำนวนบนก้อนหินสองก้อนที่อยู่ด้านล่างพอดี สังเกตว่ากฎดังกล่าวจะไม่ถูกบังคับในแถวที่เก้า จำนวนที่จะมาเติมบนก้อนหินจะต้องเป็นจำนวนเต็มเท่านั้น

รูปประกอบดูได้ที่ http://uva.onlinejudge.org/external/110/p11040.png

Input

บรรทัดแรกของข้อมูลนำเข้าระบุจำนวนเต็ม N แทนจำนวนข้อมูลชุดทดสอบ จากนั้นจะมีข้อมูลของแต่ละชุดทดสอบตามมา

แต่ละชุดทดสอบประกอบไปด้วยข้อมูล 5 บรรทัด ซึ่งจะแทนข้อมูลบนกำแพงแถวที่เป็นเลขคี่ ไล่จากแถวบนไปจนถึงแถวล่าง แถวที่ i ระบุรายการจำนวนเต็มบนแถวคี่แถวที่ i บนกำแพง ไล่จากก้อนหินด้านซ้ายไปทางด้านขวา คั่นระหว่างตัวเลขด้วยช่องว่างหนึ่งช่อง

รับประกันว่าข้อมูลชุดทดสอบนี้ถูกต้อง นั่นคือทุกข้อมูลทดสอบมีคำตอบที่เป็นไปได้

Output

สำหรับแต่ละชุดข้อมูลทดสอบ ผลลัพธ์จะประกอบด้วยข้อมูลเก้าบรรทัดระบุตัวเลขที่ปรากฏบนหินแต่ละก้อน จากแถวบนสุดไปยังแถวล่างสุด กล่าวคือ บรรทัดที่ i จะระบุตัวเลขบนแถวที่ i บนกำแพง ไล่จากซ้ายไปขวา คั่นระหว่างตัวเลขด้วยช่องว่าง

ห้ามมีช่องว่างตามหลังตัวเลขตัวสุดท้ายของแต่ละบรรทัด ไม่เช่นนั้นตัวตรวจจะระบุว่า Presentation Error

หมายเหตุ ด้านล่างแสดงตัวอย่างสองตัวอย่าง ตัวอย่างแรกเป็นตัวอย่างตามรูปประกอบ

Sample Input

2
255
54 67
10 18 13
3 3 5 2
2 1 2 1 1
256
64 64
16 16 16
4 4 4 4
1 1 1 1 1

Sample Output

255
121 134
54 67 67
23 31 36 31
10 13 18 18 13
5 5 8 10 8 5
3 2 3 5 5 3 2 
2 1 1 2 3 2 1 1
2 0 1 0 2 1 1 0 1
256
128 128
64 64 64
32 32 32 32
16 16 16 16 16
8 8 8 8 8 8
4 4 4 4 4 4 4
2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1