Arona muốn giành chức vô địch khu vực (regional championship). Vì vậy, Plana đã tạo ra bài toán sau cho Arona dựa trên từ khóa "miền" (region).
Cho ba số nguyên $n$, $m$ và $k$, bạn cần vẽ $n$ đường tròn, $m$ hình tam giác và $k$ đường thẳng trên một mặt phẳng để chia mặt phẳng đó thành nhiều miền nhất có thể.
Tất nhiên, kỹ năng vẽ và khả năng toán học của Arona rất kém. Vì vậy cô ấy tìm đến bạn để nhờ giúp đỡ.
Dữ liệu vào
Có nhiều bộ dữ liệu. Dòng đầu tiên của đầu vào chứa một số nguyên $T$ ($1 \le T \le 5 \times 10^3$) cho biết số lượng bộ dữ liệu. Đối với mỗi bộ dữ liệu:
Dòng đầu tiên và duy nhất chứa ba số nguyên $n$, $m$ và $k$ ($0 \le n, m, k \le 100$, $n + m + k > 0$) cho biết số lượng đường tròn, hình tam giác và đường thẳng.
Dữ liệu đảm bảo tổng của $(\max(n, m, k))^3$ trong tất cả các bộ dữ liệu không vượt quá $10^7$.
Dữ liệu ra
Đối với mỗi bộ dữ liệu:
Đầu tiên, in ra một dòng chứa một số nguyên, cho biết số lượng miền tối đa có thể chia được.
Sau đó in ra $n$ dòng. Mỗi dòng chứa ba số nguyên $x$, $y$ và $R$ ($-10^3 \le x, y \le 10^3$, $1 \le R \le 10^3$) cách nhau bởi một dấu cách, biểu thị tọa độ tâm và bán kính của đường tròn.
Tiếp theo, in ra $m$ dòng. Mỗi dòng chứa sáu số nguyên $x_1$, $y_1$, $x_2$, $y_2$, $x_3$ và $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)$) cách nhau bởi một dấu cách, biểu thị tọa độ ba đỉnh của hình tam giác.
Cuối cùng, in ra $k$ dòng. Mỗi dòng chứa bốn số nguyên $x_1$, $y_1$, $x_2$ và $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)$) cách nhau bởi một dấu cách, biểu thị tọa độ của hai điểm nằm trên đường thẳng.
Có thể chứng minh rằng, ngay cả với các giới hạn được nêu ở trên, ta luôn có thể đạt được đáp án tối ưu.
Ví dụ
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
Ghi chú
Bộ dữ liệu ví dụ thứ ba được minh họa ở dưới đây.

