Arona ต้องการคว้าแชมป์ระดับภูมิภาค (regional championship) ดังนั้น Plana จึงสร้างโจทย์ต่อไปนี้ให้กับ Arona โดยอิงจากคำสำคัญว่า "อาณาบริเวณ" (region)
กำหนดจำนวนเต็มสามจำนวนคือ $n$, $m$ และ $k$ คุณต้องวาดวงกลม $n$ วง รูปสามเหลี่ยม $m$ รูป และเส้นตรง $k$ เส้นลงบนระนาบ เพื่อแบ่งระนาบออกเป็นอาณาบริเวณย่อยๆ ให้ได้มากที่สุดเท่าที่จะเป็นไปได้
แน่นอนว่าทักษะการวาดภาพและความสามารถทางคณิตศาสตร์ของ Arona นั้นแย่มาก เธอจึงมาขอความช่วยเหลือจากคุณ
ข้อมูลนำเข้า
มีหลายกรณีทดสอบ บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 5 \times 10^3$) แทนจำนวนกรณีทดสอบ สำหรับแต่ละกรณีทดสอบ:
บรรทัดแรกและบรรทัดเดียวประกอบด้วยจำนวนเต็มสามจำนวนคือ $n$, $m$ และ $k$ ($0 \le n, m, k \le 100$, $n + m + k > 0$) แทนจำนวนวงกลม รูปสามเหลี่ยม และเส้นตรง
รับประกันว่าผลรวมของ $(\max(n, m, k))^3$ จากทุกกรณีทดสอบไม่เกิน $10^7$
ข้อมูลส่งออก
สำหรับแต่ละกรณีทดสอบ:
ขั้นแรก ให้แสดงผลหนึ่งบรรทัดที่ประกอบด้วยจำนวนเต็มหนึ่งจำนวน แทนจำนวนอาณาบริเวณสูงสุดที่สามารถแบ่งได้
จากนั้นแสดงผล $n$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสามจำนวนคือ $x$, $y$ และ $R$ ($-10^3 \le x, y \le 10^3$, $1 \le R \le 10^3$) คั่นด้วยช่องว่าง แทนพิกัดของจุดศูนย์กลางของวงกลมรวมถึงรัศมีของวงกลม
ถัดไปแสดงผล $m$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มหกจำนวนคือ $x_1$, $y_1$, $x_2$, $y_2$, $x_3$ และ $y_3$ ($-10^3 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 10^3$, $(x_1, y_1) \ne (x_2, y_2)$, $(x_1, y_1) \ne (x_3, y_3)$, $(x_2, y_2) \ne (x_3, y_3)$) คั่นด้วยช่องว่าง แทนพิกัดของจุดยอดทั้งสามของรูปสามเหลี่ยม
สุดท้ายแสดงผล $k$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสี่จำนวนคือ $x_1$, $y_1$, $x_2$ และ $y_2$ ($-10^3 \le x_1, y_1, x_2, y_2 \le 10^3$, $(x_1, y_1) \ne (x_2, y_2)$) คั่นด้วยช่องว่าง แทนพิกัดของจุดสองจุดบนเส้นตรง
สามารถพิสูจน์ได้ว่า แม้จะมีข้อจำกัดตามที่ระบุไว้ข้างต้น เราก็ยังสามารถหาคำตอบที่เหมาะสมที่สุดได้เสมอ
ตัวอย่าง
3
1 0 1
0 1 1
1 1 2
4
0 0 1
-2 0 2 0
4
0 0 0 2 2 0
0 1 1 0
18
3 4 2
2 7 2 1 6 4
3 4 6 4
3 3 3 5
หมายเหตุ
กรณีทดสอบตัวอย่างที่สามแสดงอยู่ด้านล่างนี้

