題目描述

給定平面上的一條直線，請構造一個頂點為整點的三角形，使得其歐拉線與給定的直線重合。

我們來回顧一下基本定義。設 $\triangle ABC$ 是平面上的一個非退化三角形，$M_A$、$M_B$ 和 $M_C$ 分別是邊 $BC$、$AC$ 和 $AB$ 的中點，$s_A$、$s_B$ 和 $s_C$ 分別是邊 $BC$、$AC$ 和 $AB$ 的垂直平分線。形式化地，$s_A$ 是過點 $M_A$ 且垂直於直線 $BC$ 的直線；直線 $s_B$ 和 $s_C$ 的定義類似。由中學幾何可知，直線 $s_A$、$s_B$ 和 $s_C$ 交於單一點 $O$。點 $O$ 具有一個顯著的性質，即它到三角形的三個頂點 $A$、$B$ 和 $C$ 的距離相等。以 $O$ 為圓心、$OA$ 為半徑的圓稱為三角形 $ABC$ 的外接圓，它是平面上唯一通過該三角形所有三個頂點的圓。點 $O$ 被稱為三角形 $ABC$ 的外心。

設 $H_A$、$H_B$ 和 $H_C$ 分別表示頂點 $A$、$B$ 和 $C$ 在直線 $BC$、$AC$ 和 $AB$ 上的正交投影。線段 $AH_A$、$BH_B$ 和 $CH_C$ 稱為三角形 $ABC$ 的高。由中學幾何可知，直線 $AH_A$、$BH_B$ 和 $CH_C$ 交於單一點 $H$，稱為三角形 $ABC$ 的垂心。在銳角或直角三角形中，$H$ 位於高線段本身上，而在鈍角三角形中，它位於高線段的延長線上。

線段 $AM_A$、$BM_B$ 和 $CM_C$ 稱為三角形的中線。由中學幾何可知，中線交於單一點 $G$，稱為三角形 $ABC$ 的重心。三角形 $M_A M_B M_C$ 稱為三角形 $ABC$ 的中點三角形。上述概念同樣適用於它：因此，點 $G$ 是中點三角形的重心，而 $O$ 是中點三角形的垂心。三角形 $M_A M_B M_C$ 的外接圓通過 $M_A$、$M_B$、$M_C$、$H_A$、$H_B$、$H_C$ 以及線段 $AH$、$BH$、$CH$ 的中點，因此它被稱為三角形 $ABC$ 的九點圓，其圓心記為 $O_9$。

在等邊三角形中，點 $O$、$H$、$G$ 和 $O_9$ 重合。在任何其他三角形中，它們兩兩不同，但它們共線，這條直線稱為三角形 $ABC$ 的歐拉線。這四個點在歐拉線上的排列順序也是已知的：$O_9$ 總是線段 $OH$ 的中點，且點 $G$ 位於線段 $OH$ 上，並將線段 $OH$ 分成 $2 : 1$ 的比例（其中 $G$ 到 $O$ 的距離是到 $H$ 的距離的一半）。

你需要構造一個頂點為整點的非退化三角形 $ABC$，使得 $O$、$H$、$G$ 和 $O_9$ 落在給定的直線上，或者報告這是不可能的。

輸入格式

第一行包含一個整數 $t$，表示測試用例的數量（$1 \le t \le 5 \cdot 10^5$）。

在每個測試用例描述的唯一一行中，包含三個整數 $k$、$\ell$ 和 $m$，表示直線的係數（$-10^3 \le k, \ell, m \le 10^3$）。該直線定義為滿足方程 $kx + \ell y + m = 0$ 的點 $(x, y)$ 的集合。保證 $k^2 + \ell^2 > 0$。

輸出格式

對於每個測試用例，輸出六個整數 $A_x, A_y, B_x, B_y, C_x, C_y$，表示一個非退化三角形的頂點座標。必須滿足條件 $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$。三角形 $ABC$ 的歐拉線方程必須為 $kx + \ell y + m = 0$。如果不存在這樣的三角形，則輸出六個由空格分隔的零。

在評測系統提供的每個測試用例中，均保證如果存在至少一個頂點為整點且具有給定歐拉線的三角形 $ABC$，則也存在一個滿足條件 $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$ 的三角形。

範例

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

說明

我們沒有顯式要求 $\triangle ABC$ 為非等邊三角形，因為不可能構造出頂點均為整點的等邊三角形。