Beschreibung

Gegeben sei eine Gerade in der Ebene. Konstruiere ein Dreieck mit ganzzahligen Eckpunktkoordinaten, sodass seine eulersche Gerade mit der gegebenen Geraden übereinstimmt.

Rufen wir uns die grundlegenden Definitionen in Erinnerung. Sei $\triangle ABC$ ein nicht-entartetes Dreieck in der Ebene, seien $M_A$, $M_B$ und $M_C$ die Mittelpunkte der Seiten $BC$, $AC$ bzw. $AB$, und seien $s_A$, $s_B$ und $s_C$ die Mittelsenkrechten der Seiten $BC$, $AC$ und $AB$. Formal ist $s_A$ das im Punkt $M_A$ errichtete Lot auf die Gerade $BC$; die Geraden $s_B$ und $s_C$ sind analog definiert. Aus der Schulgeometrie ist bekannt, dass sich die Geraden $s_A$, $s_B$ und $s_C$ in einem einzigen Punkt $O$ schneiden. Der Punkt $O$ besitzt eine bemerkenswerte Eigenschaft: Er ist von allen drei Eckpunkten $A$, $B$ und $C$ gleich weit entfernt. Der Kreis mit Mittelpunkt $O$ und Radius $OA$ heißt Umkreis des Dreiecks $ABC$, und er ist der einzige Kreis in der Ebene, der durch alle drei Eckpunkte des Dreiecks verläuft. Der Punkt $O$ wird als Umkreismittelpunkt des Dreiecks $ABC$ bezeichnet.

Seien $H_A$, $H_B$ und $H_C$ die Orthogonalprojektionen der Eckpunkte $A$, $B$ und $C$ auf die Geraden $BC$, $AC$ bzw. $AB$. Die Strecken $AH_A$, $BH_B$ und $CH_C$ heißen Höhen des Dreiecks $ABC$. Aus der Schulgeometrie ist bekannt, dass sich die Geraden $AH_A$, $BH_B$ und $CH_C$ in einem einzigen Punkt $H$ schneiden, der Höhenschnittpunkt (Orthozentrum) des Dreiecks $ABC$ genannt wird. In einem spitzwinkligen oder rechtwinkligen Dreieck liegt $H$ auf den Höhen selbst, während er in einem stumpfwinkligen Dreieck auf deren Verlängerungen liegt.

Die Strecken $AM_A$, $BM_B$ und $CM_C$ heißen Seitenhalbierende (Medianen) des Dreiecks. Aus der Schulgeometrie ist bekannt, dass sich die Seitenhalbierenden in einem einzigen Punkt $G$ schneiden, der Schwerpunkt (Baryzentrum) des Dreiecks $ABC$ genannt wird. Das Dreieck $M_A M_B M_C$ heißt Mittendreieck des Dreiecks $ABC$. Die obigen Begriffe gelten auch für dieses: Somit ist der Punkt $G$ der Schwerpunkt des Mittendreiecks und $O$ der Höhenschnittpunkt des Mittendreiecks. Der Umkreis des Dreiecks $M_A M_B M_C$ verläuft durch $M_A$, $M_B$, $M_C$, $H_A$, $H_B$, $H_C$ sowie durch die Mittelpunkte der Strecken $AH$, $BH$, $CH$, weshalb er Neun-Punkte-Kreis (Feuerbach-Kreis) des Dreiecks $ABC$ genannt wird; sein Mittelpunkt wird mit $O_9$ bezeichnet.

In einem gleichseitigen Dreieck fallen die Punkte $O$, $H$, $G$ und $O_9$ zusammen. In jedem anderen Dreieck sind sie paarweise verschieden, liegen aber auf einer einzigen Geraden, die eulersche Gerade des Dreiecks $ABC$ genannt wird. Die Anordnung dieser vier Punkte auf der eulerschen Geraden ist ebenfalls bekannt: $O_9$ ist stets der Mittelpunkt der Strecke $OH$, und der Punkt $G$ liegt auf der Strecke $OH$ und teilt sie im Verhältnis $2 : 1$ (wobei $G$ doppelt so nah an $O$ liegt wie an $H$).

Du sollst ein nicht-entartetes Dreieck $ABC$ mit ganzzahligen Eckpunktkoordinaten konstruieren, sodass $O$, $H$, $G$ und $O_9$ auf der gegebenen Geraden liegen, oder melden, dass dies unmöglich ist.

Eingabe

Die erste Zeile enthält eine ganze Zahl $t$, die Anzahl der Testfälle ($1 \le t \le 5 \cdot 10^5$).

In der einzigen Zeile der Beschreibung jedes Testfalls stehen drei ganze Zahlen $k$, $\ell$ und $m$, welche die Koeffizienten der Geraden angeben ($-10^3 \le k, \ell, m \le 10^3$). Die Gerade ist definiert als die Menge der Punkte $(x, y)$, welche die Gleichung $kx + \ell y + m = 0$ erfüllen. Es wird garantiert, dass $k^2 + \ell^2 > 0$ gilt.

Ausgabe

Gib für jeden Testfall sechs ganze Zahlen $A_x, A_y, B_x, B_y, C_x, C_y$ aus, welche die Koordinaten der Eckpunkte eines nicht-entarteten Dreiecks bezeichnen. Die Bedingungen $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$ müssen erfüllt sein. Die eulersche Gerade des Dreiecks $ABC$ muss die Gleichung $kx + \ell y + m = 0$ haben. Falls ein solches Dreieck nicht existiert, gib sechs durch Leerzeichen getrennte Nullen aus.

In jedem der von der Jury bereitgestellten Tests ist garantiert: Wenn mindestens ein Dreieck $ABC$ mit ganzzahligen Eckpunkten und der gegebenen eulerschen Geraden existiert, dann gibt es auch ein Dreieck, das die Bedingungen $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$ erfüllt.

Beispiel

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

Hinweis

Wir fordern nicht explizit, dass $\triangle ABC$ nicht gleichseitig ist, da es unmöglich ist, ein gleichseitiges Dreieck zu konstruieren, dessen Eckpunkte ganzzahlige Koordinaten haben.