Lýsing

Gefin er lína í sléttunni. Smíðið þríhyrning með hornpunkta í heiltölupunktum þannig að Euler-lína hans falli saman við gefnu línuna.

Rifjum upp helstu skilgreiningar. Látum $\triangle ABC$ vera óúrkynjaðan þríhyrning í sléttunni, $M_A$, $M_B$ og $M_C$ vera miðpunkta hliðanna $BC$, $AC$ og $AB$, í þessari röð, og $s_A$, $s_B$ og $s_C$ vera miðþverla hliðanna $BC$, $AC$ og $AB$. Formlega er $s_A$ þverillinn á línuna $BC$ sem dreginn er í punktinum $M_A$; línurnar $s_B$ og $s_C$ eru skilgreindar á svipaðan hátt. Úr skólarúmfræði er þekkt að línurnar $s_A$, $s_B$ og $s_C$ skerast í einum punkti $O$. Punkturinn $O$ hefur þann merkilega eiginleika að vera í sömu fjarlægð frá öllum þremur hornpunktunum $A$, $B$ og $C$. Hringurinn með miðju í $O$ og geisla $OA$ kallast umhringur þríhyrningsins $ABC$, og hann er eini hringurinn í sléttunni sem fer í gegnum alla þrjá hornpunkta þríhyrningsins. Punkturinn $O$ er nefndur ummiðja þríhyrningsins $ABC$.

Látum $H_A$, $H_B$ og $H_C$ tákna hornrétt ofanvörp hornpunktanna $A$, $B$ og $C$ á línurnar $BC$, $AC$ og $AB$, í þessari röð. Strikinn $AH_A$, $BH_B$ og $CH_C$ kallast hæðir þríhyrningsins $ABC$. Úr skólarúmfræði er þekkt að línurnar $AH_A$, $BH_B$ og $CH_C$ skerast í einum punkti $H$, sem kallast hæðamiðja þríhyrningsins $ABC$. Í hvasshyrndum eða rétthyrndum þríhyrningi liggur $H$ á hæðunum sjálfum, en í gleiðhyrndum þríhyrningi liggur hann á framlengingum þeirra.

Strikinn $AM_A$, $BM_B$ og $CM_C$ kallast miðlínur þríhyrningsins. Úr skólarúmfræði er þekkt að miðlínurnar skerast í einum punkti $G$, sem kallast þungamiðja þríhyrningsins $ABC$. Þríhyrningurinn $M_A M_B M_C$ kallast miðpunktaþríhyrningur þríhyrningsins $ABC$. Hugtökin hér að ofan eiga einnig við um hann: þannig er punkturinn $G$ þungamiðja miðpunktaþríhyrningsins og $O$ er hæðamiðja miðpunktaþríhyrningsins. Umhringur þríhyrningsins $M_A M_B M_C$ fer í gegnum $M_A$, $M_B$, $M_C$, $H_A$, $H_B$, $H_C$, sem og í gegnum miðpunkta strikanna $AH$, $BH$, $CH$, og þess vegna kallast hann níu punkta hringur þríhyrningsins $ABC$, og miðja hans er táknuð með $O_9$.

Í jafnhliða þríhyrningi falla punktarnir $O$, $H$, $G$ og $O_9$ saman. Í öllum öðrum þríhyrningum eru þeir parvísi ólíkir, en þeir liggja á einni línu sem kallast Euler-lína þríhyrningsins $ABC$. Röðun þessara fjögurra punkta á Euler-línunni er einnig þekkt: $O_9$ er alltaf miðpunktur striksins $OH$, og punkturinn $G$ liggur á strikinu $OH$ og skiptir því í hlutfallinu $2 : 1$ (þar sem $G$ er tvöfalt nær $O$ en $H$).

Þú átt að smíða óúrkynjaðan þríhyrning $ABC$ með hornpunkta í heiltölupunktum, þannig að $O$, $H$, $G$ og $O_9$ liggi á gefnu línunni, eða tilkynna að það sé ómögulegt.

Inntak

Fyrsta línan inniheldur heiltölu $t$, fjölda prófunartilvika ($1 \le t \le 5 \cdot 10^5$).

Í einu línu lýsingarinnar á hverju prófunartilviki eru þrjár heiltölur, $k$, $\ell$ og $m$, sem tákna stuðla línunnar ($-10^3 \le k, \ell, m \le 10^3$). Línan er skilgreind sem mengi punkta $(x, y)$ sem uppfylla jöfnuna $kx + \ell y + m = 0$. Tryggt er að $k^2 + \ell^2 > 0$.

Úttak

Fyrir hvert prófunartilvik skaltu prenta sex heiltölur $A_x, A_y, B_x, B_y, C_x, C_y$, sem tákna hnit hornpunkta óúrkynjaðs þríhyrnings. Skilyrðin $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$ verða að vera uppfyllt. Euler-lína þríhyrningsins $ABC$ verður að hafa jöfnuna $kx + \ell y + m = 0$. Ef slíkur þríhyrningur er ekki til skaltu prenta sex núll aðskilin með bilum.

Í hverju prófi sem dómnefndin leggur fyrir er tryggt að ef til er að minnsta kosti einn þríhyrningur $ABC$ með heiltöluhornpunkta sem hefur gefnu Euler-línuna, þá er einnig til þríhyrningur sem uppfyllir skilyrðin $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$.

Dæmi

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

Athugasemd

Við krefjumst þess ekki sérstaklega að $\triangle ABC$ sé ekki jafnhliða vegna þess að ómögulegt er að búa til jafnhliða þríhyrning þar sem hornpunktarnir hafa heiltöluhnit.