Una กำลังเดินอยู่บนเส้นทางที่มีต้นซากุระ $n$ ต้น เศษเสี้ยวของฤดูใบไม้ผลิร่วงหล่นลงมาจากท้องฟ้าอย่างแผ่วเบา บนต้นซากุระต้นที่ $i$ มีดอกไม้บานอยู่ $a_i$ ดอก
Una คิดถึง Kamome เพื่อนสนิทที่สุดของเธอมาก เธอจำได้ว่าในวันที่ Kamome จากเมืองนี้ไป Kamome ได้มอบลำดับจำนวนเต็ม $b_1, \dots, b_n$ ให้กับ Una โดย Kamome บอก Una ว่าเมื่อ $a_i \equiv b_i \pmod 2$ สำหรับทุก $i \in [1, n]$ พลังเวทมนตร์ในต้นซากุระจะทำงานและพวกเธอจะได้พบกันอีกครั้ง
ความปรารถนาของ Una แรงกล้ามากจนจินตนาการของเธอกลายเป็นความจริง เธอได้รับพลังเวทมนตร์ที่ทำให้ดอกไม้ผลิบานได้ ในการโบกไม้กายสิทธิ์แต่ละครั้ง เธอสามารถเลือกลำดับย่อยติดกันของต้นซากุระ $[l, r]$ และเปลี่ยนค่า $a_i$ เป็น $\sum_{j=l}^i a_j$ สำหรับทุก $i \in [l, r]$
ด้วยพรสวรรค์ด้านเวทมนตร์ Una สามารถร่ายเวทมนตร์ได้ไม่จำกัดจำนวนครั้งในแต่ละวัน แต่เธอต้องไม่ร่ายเวทมนตร์ใส่ต้นไม้ต้นเดิมตั้งแต่สองครั้งขึ้นไปในวันเดียวกัน มิฉะนั้นต้นไม้จะตายเนื่องจากได้รับพลังเวทมนตร์มากเกินไป (กล่าวอีกนัยหนึ่งคือ ลำดับย่อยที่เลือกในวันเดียวกันจะต้องไม่ทับซ้อนกัน)
Una ไม่ได้พบ Kamome มาสิบปีแล้ว และเธอไม่ต้องการรออีกต่อไป Una ต้องการทราบจำนวนวันที่น้อยที่สุดที่พวกเธอจะได้พบกัน (กล่าวคือ ทำให้ $a_i \equiv b_i \pmod 2$ สำหรับแต่ละ $i \in [1, n]$) และเวทมนตร์ที่เธอควรร่ายในแต่ละวันเพื่อให้ได้จำนวนวันน้อยที่สุดนี้ สังเกตว่าอาจเป็นไปไม่ได้ ซึ่งในกรณีนั้นคุณควรบอกเธอ (โปรดดูรายละเอียดเพิ่มเติมในส่วนข้อมูลส่งออก)
ข้อมูลนำเข้า
แต่ละชุดการทดสอบประกอบด้วยหลายชุดข้อมูลทดสอบ บรรทัดแรกประกอบด้วยจำนวนชุดข้อมูลทดสอบ $t$ ($1 \le t \le 2.5 \times 10^4$) รายละเอียดของแต่ละชุดข้อมูลทดสอบมีดังต่อไปนี้
บรรทัดแรกของแต่ละชุดข้อมูลทดสอบมีจำนวนเต็มหนึ่งจำนวนคือ $n$ ($1 \le n \le 10^3$, $\sum n^2 \le 10^6$) แทนจำนวนต้นซากุระ
บรรทัดที่สองของแต่ละชุดข้อมูลทดสอบมีจำนวนเต็ม $n$ จำนวนคือ $a_1, \dots, a_n$ ($0 \le a_i \le 1$) แทนจำนวนดอกไม้บนแต่ละต้นในปัจจุบัน
บรรทัดที่สามของแต่ละชุดข้อมูลทดสอบมีจำนวนเต็ม $n$ จำนวนคือ $b_1, \dots, b_n$ ($0 \le b_i \le 1$) แทนลำดับที่ Kamome มอบให้ Una
ข้อมูลส่งออก
สำหรับแต่ละชุดข้อมูลทดสอบ หากไม่สามารถทำให้ Kamome และ Una ได้พบกันได้ ให้พิมพ์ -1 มิฉะนั้นให้พิมพ์จำนวนเต็มหนึ่งจำนวนคือ $k$ แทนจำนวนวันที่น้อยที่สุดที่ Una ต้องใช้เพื่อจะได้พบกับ Kamome
ในบรรทัดที่ $i$ ของอีก $k$ บรรทัดถัดไป คุณต้องระบุคำแนะนำให้ Una เกี่ยวกับเวทมนตร์ที่เธอควรร่ายในวันที่ $i$ โดยพิมพ์จำนวนเต็ม $2c + 1$ จำนวน ได้แก่ $c_i, l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}, \dots, l_{i,c}, r_{i,c}$ เมื่อ $c$ คือจำนวนครั้งของการใช้เวทมนตร์ที่เธอควรทำในวันที่ $i$ และ $[l_{i,j}, r_{i,j}]$ แทนลำดับย่อยติดกันลำดับที่ $j$ ที่เธอควรเลือกในวันที่ $i$ คุณต้องรับประกันว่า $r_i < l_{i+1}$ สำหรับทุก $1 \le i \le c - 1$ และ $l_i \le r_i$ สำหรับทุก $1 \le i \le c$
หากมีคำตอบที่ถูกต้องหลายแบบ คุณสามารถแสดงคำตอบใดก็ได้
ตัวอย่าง
ข้อมูลนำเข้า
3 5 1 0 1 0 1 0 1 0 1 0 3 1 1 0 1 1 1 10 1 0 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0
ข้อมูลส่งออก
-1 1 1 2 3 2 2 1 4 6 9 2 1 2 6 7
หมายเหตุ
ในชุดข้อมูลทดสอบที่สาม เมื่อสิ้นสุดวันแรก ลำดับ $a$ คือ $[\underline{1, 1, 1, 2}, 0, \underline{1, 1, 1, 2}, 0]$
เมื่อสิ้นสุดวันที่สอง ลำดับ $a$ คือ $[\underline{1, 2}, 1, 2, 0, \underline{1, 2}, 1, 2, 0]$
เห็นได้ชัดว่าหลังจากผ่านไปสองวัน $a_i \equiv b_i \pmod 2$ สามารถพิสูจน์ได้ว่าไม่สามารถทำให้สำเร็จได้ภายในหนึ่งวัน