Ontak-07-hyperclock

Hyperclock

Source: [1]

Brainy Smurf ได้สรุปว่าวันหนึ่งนั้นช่างสั้นยิ่งนัก เขาจึงเขียนหนังสือ Quotations of Brainy Smurf ไม่จบสักที เขาตัดสินใจที่จะไปพบกับ Father Time เพื่อขอร้องให้เพิ่มเวลาในแต่ละวันเป็น 48 ชั่วโมง Father Time ไม่ต้องการทำตามคำขอ จึงได้บอกให้ Brainy Smurf แก้ปริศนา Hyperclock ให้ได้เสียก่อย

Hyperclock ประกอบไปด้วยนาฬิกา N เรือน แต่ละเรือนมีเข็มนาฬิกาเดียวและมีตัวเลขอยู่บนนั้น สำหรับ 1 <= i <= N จะมีตัวเลข 1 ถึง ki เมื่อเริ่มต้น เข็มนาฬิกาทุกเรือนจะชี้ที่เลข 1 เงื่อนไขขอปริศนาเป็นดังนี้

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

ช่วยเขาหน่อย!

Input

บรรทัดแรกจะมีจำนวนเต็มหนึ่งจำนวนคือ N จากนั้นแต่ละบรรทัดถัดไปจะระบุจำนวนเต็มหนึ่งจำนวนที่มีค่ามากกว่า 1 กล่าวคือ ในบรรทัดที่ i+1 จะระบุจำนวนเต็ม ki จำนวนรูปแบบที่เป็นไปได้ นั่นคือ k1 x k2 x k3 x ... x kN จะมีค่าไม่เกิน 10⁶

Output

ถ้าไม่มีคำตอบให้พิมพ์ NIE ไม่ใช่นั้น ให้พิมพ์คำตอบจำนวน k1 x k2 x k3 x ... x kN แถว แต่ละแถวระบุจำนวนเต็มสองจำนวน จำนวนแรกคือหมายเลขของนาฬิกาที่จะหมุน จำนวนที่สองระบุทิศทาง โดยที่ 1 แทนทิศตามเข็มนาฬิกา และ -1 แทนทิศทวนเข็มนาฬิกา ถ้ามีคำตอบที่เป็นไปได้หลายแบบ คุณสามารถตอบแบบใดก็ได้

ตัวอย่าง

สำหรับข้อมูลนำเข้า:

3
2
2
3

คำตอบหนึ่งที่เป็นไปได้คือ:

1 1
2 1
1 -1
3 1
1 1
2 -1
3 1
2 1
1 -1
2 -1
3 -1
3 -1

Task author: Jakub Pawlewicz (story by Tomasz Idziaszek).