Description

Étant donné une droite du plan, construisez un triangle dont les sommets sont à coordonnées entières tel que sa droite d'Euler coïncide avec la droite donnée.

Rappelons les définitions de base. Soit $\triangle ABC$ un triangle non dégénéré du plan, $M_A$, $M_B$ et $M_C$ les milieux respectifs des côtés $BC$, $AC$ et $AB$, et $s_A$, $s_B$ et $s_C$ les médiatrices des côtés $BC$, $AC$ et $AB$. Formellement, $s_A$ est la perpendiculaire à la droite $BC$ passant par le point $M_A$ ; les droites $s_B$ et $s_C$ sont définies de manière analogue. D'après la géométrie élémentaire, on sait que les droites $s_A$, $s_B$ et $s_C$ se coupent en un unique point $O$. Le point $O$ possède une propriété remarquable : il est équidistant des trois sommets $A$, $B$ et $C$. Le cercle de centre $O$ et de rayon $OA$ est appelé le cercle circonscrit au triangle $ABC$, et c'est l'unique cercle du plan qui passe par les trois sommets du triangle. Le point $O$ est appelé le centre du cercle circonscrit au triangle $ABC$.

Soient $H_A$, $H_B$ et $H_C$ les projections orthogonales respectives des sommets $A$, $B$ et $C$ sur les droites $BC$, $AC$ et $AB$. Les segments $AH_A$, $BH_B$ et $CH_C$ sont appelés les hauteurs du triangle $ABC$. D'après la géométrie élémentaire, on sait que les droites $AH_A$, $BH_B$ et $CH_C$ se coupent en un unique point $H$, appelé l'orthocentre du triangle $ABC$. Dans un triangle acutangle ou rectangle, $H$ se trouve sur les hauteurs elles-mêmes, tandis que dans un triangle obtusangle, il se trouve sur leurs prolongements.

Les segments $AM_A$, $BM_B$ et $CM_C$ sont appelés les médianes du triangle. D'après la géométrie élémentaire, on sait que les médianes se coupent en un unique point $G$, appelé le centre de gravité ou barycentre du triangle $ABC$. Le triangle $M_A M_B M_C$ est appelé le triangle médian du triangle $ABC$. Les concepts ci-dessus s'appliquent également à lui : ainsi, le point $G$ est le barycentre du triangle médian, et $O$ est l'orthocentre du triangle médian. Le cercle circonscrit au triangle $M_A M_B M_C$ passe par $M_A$, $M_B$, $M_C$, $H_A$, $H_B$, $H_C$, ainsi que par les milieux des segments $AH$, $BH$, $CH$, raison pour laquelle on l'appelle le cercle des neuf points du triangle $ABC$, et son centre est noté $O_9$.

Dans un triangle équilatéral, les points $O$, $H$, $G$ et $O_9$ sont confondus. Dans tout autre triangle, ils sont deux à deux distincts, mais ils sont alignés sur une même droite, appelée la droite d'Euler du triangle $ABC$. La disposition de ces quatre points sur la droite d'Euler est également connue : $O_9$ est toujours le milieu du segment $OH$, et le point $G$ appartient au segment $OH$ et le partage dans le rapport $2 : 1$ ($G$ étant deux fois plus proche de $O$ que de $H$).

On vous demande de construire un triangle non dégénéré $ABC$ dont les sommets sont à coordonnées entières, tel que $O$, $H$, $G$ et $O_9$ appartiennent à la droite donnée, ou d'indiquer que cela est impossible.

Entrée

La première ligne contient un entier $t$, le nombre de cas de test ($1 \le t \le 5 \cdot 10^5$).

Dans l'unique ligne décrivant chaque cas de test, il y a trois entiers $k$, $\ell$ et $m$, désignant les coefficients de la droite ($-10^3 \le k, \ell, m \le 10^3$). La droite est définie comme l'ensemble des points $(x, y)$ qui vérifient l'équation $kx + \ell y + m = 0$. Il est garanti que $k^2 + \ell^2 > 0$.

Sortie

Pour chaque cas de test, affichez six entiers $A_x, A_y, B_x, B_y, C_x, C_y$, désignant les coordonnées des sommets d'un triangle non dégénéré. Les conditions $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$ doivent être satisfaites. La droite d'Euler du triangle $ABC$ doit avoir pour équation $kx + \ell y + m = 0$. Si un tel triangle n'existe pas, affichez six zéros séparés par des espaces.

Dans chacun des tests fournis par le jury, il est garanti que s'il existe au moins un triangle $ABC$ à sommets entiers ayant la droite d'Euler donnée, alors il existe également un triangle satisfaisant les conditions $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$.

Exemple

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

Note

Nous n'exigeons pas explicitement que $\triangle ABC$ soit non équilatéral car il est impossible de construire un triangle équilatéral dont les sommets ont des coordonnées entières.