Mô tả

Cho một đường thẳng trên mặt phẳng, hãy dựng một tam giác có các đỉnh tại các điểm nguyên sao cho đường thẳng Euler của nó trùng với đường thẳng đã cho.

Hãy nhắc lại các định nghĩa cơ bản. Giả sử $\triangle ABC$ là một tam giác không suy biến trên mặt phẳng, $M_A$, $M_B$ và $M_C$ lần lượt là trung điểm của các cạnh $BC$, $AC$ và $AB$, còn $s_A$, $s_B$ và $s_C$ là các đường trung trực của các cạnh $BC$, $AC$ và $AB$. Một cách hình thức, $s_A$ là đường thẳng vuông góc với đường thẳng $BC$ kẻ tại điểm $M_A$; các đường thẳng $s_B$ và $s_C$ được định nghĩa tương tự. Từ hình học phổ thông, ta biết rằng các đường thẳng $s_A$, $s_B$ và $s_C$ cắt nhau tại một điểm duy nhất $O$. Điểm $O$ có một tính chất đáng chú ý là nó cách đều cả ba đỉnh $A$, $B$ và $C$. Đường tròn tâm $O$ bán kính $OA$ được gọi là đường tròn ngoại tiếp của tam giác $ABC$, và đó là đường tròn duy nhất trong mặt phẳng đi qua cả ba đỉnh của tam giác. Điểm $O$ được gọi là tâm đường tròn ngoại tiếp của tam giác $ABC$.

Gọi $H_A$, $H_B$ và $H_C$ lần lượt là hình chiếu vuông góc của các đỉnh $A$, $B$ và $C$ lên các đường thẳng $BC$, $AC$ và $AB$. Các đoạn thẳng $AH_A$, $BH_B$ và $CH_C$ được gọi là các đường cao của tam giác $ABC$. Từ hình học phổ thông, ta biết rằng các đường thẳng $AH_A$, $BH_B$ và $CH_C$ cắt nhau tại một điểm duy nhất $H$, được gọi là trực tâm của tam giác $ABC$. Trong tam giác nhọn hoặc tam giác vuông, $H$ nằm ngay trên các đoạn đường cao, trong khi ở tam giác tù, nó nằm trên phần kéo dài của chúng.

Các đoạn thẳng $AM_A$, $BM_B$ và $CM_C$ được gọi là các đường trung tuyến của tam giác. Từ hình học phổ thông, ta biết rằng các đường trung tuyến cắt nhau tại một điểm duy nhất $G$, được gọi là trọng tâm của tam giác $ABC$. Tam giác $M_A M_B M_C$ được gọi là tam giác trung bình của tam giác $ABC$. Các khái niệm trên cũng áp dụng cho nó: do đó, điểm $G$ là trọng tâm của tam giác trung bình, và $O$ là trực tâm của tam giác trung bình. Đường tròn ngoại tiếp của tam giác $M_A M_B M_C$ đi qua $M_A$, $M_B$, $M_C$, $H_A$, $H_B$, $H_C$, cũng như qua trung điểm của các đoạn thẳng $AH$, $BH$, $CH$, đó là lý do tại sao nó được gọi là đường tròn chín điểm (đường tròn Euler) của tam giác $ABC$, và tâm của nó được ký hiệu là $O_9$.

Trong một tam giác đều, các điểm $O$, $H$, $G$ và $O_9$ trùng nhau. Trong bất kỳ tam giác nào khác, chúng đôi một phân biệt nhưng cùng nằm trên một đường thẳng duy nhất, được gọi là đường thẳng Euler của tam giác $ABC$. Thứ tự sắp xếp của bốn điểm này trên đường thẳng Euler cũng đã biết: $O_9$ luôn là trung điểm của đoạn thẳng $OH$, và điểm $G$ nằm trên đoạn thẳng $OH$ và chia nó theo tỷ lệ $2 : 1$ (với $G$ gần $O$ gấp đôi so với $H$).

Bạn được yêu cầu dựng một tam giác không suy biến $ABC$ có các đỉnh tại các điểm nguyên, sao cho $O$, $H$, $G$ và $O_9$ nằm trên đường thẳng đã cho, hoặc cho biết rằng điều này là không thể.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$, số lượng bộ dữ liệu ($1 \le t \le 5 \cdot 10^5$).

Trên dòng duy nhất mô tả mỗi bộ dữ liệu, có ba số nguyên $k$, $\ell$ và $m$, biểu thị các hệ số của đường thẳng ($-10^3 \le k, \ell, m \le 10^3$). Đường thẳng được định nghĩa là tập hợp các điểm $(x, y)$ thỏa mãn phương trình $kx + \ell y + m = 0$. Đảm bảo rằng $k^2 + \ell^2 > 0$.

Dữ liệu ra

Với mỗi bộ dữ liệu, hãy in ra sáu số nguyên $A_x, A_y, B_x, B_y, C_x, C_y$, biểu thị tọa độ các đỉnh của một tam giác không suy biến. Các điều kiện $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$ phải được thỏa mãn. Đường thẳng Euler của tam giác $ABC$ phải có phương trình $kx + \ell y + m = 0$. Nếu không tồn tại tam giác như vậy, hãy in ra sáu số không cách nhau bởi dấu cách.

Trong mỗi bộ dữ liệu do ban giám khảo cung cấp, đảm bảo rằng nếu tồn tại ít nhất một tam giác $ABC$ có các đỉnh nguyên với đường thẳng Euler đã cho, thì cũng tồn tại một tam giác thỏa mãn điều kiện $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$.

Ví dụ

8
0 1 0
1 0 1
-1 1 -2
3 4 8
1 1 1
8 4 2
27 9 3
-544 862 12

-1 -1 -1 1 0 0
-2 -2 -2 2 1 -1
-2 -1 -2 2 0 1
-4 -3 2 -4 2 1
-1 -1 -1 0 0 0
0 0 0 0 0 0
-4 0 3 -2 0 4
5811 -1154 -3261 -2058 -3713 2478

Ghi chú

Chúng tôi không yêu cầu tường minh $\triangle ABC$ phải là tam giác không đều bởi vì không thể tạo ra một tam giác đều mà các đỉnh có tọa độ nguyên.