Descripción

Dada una recta en el plano, construye un triángulo con vértices en puntos enteros tal que su recta de Euler coincida con la recta dada.

Recordemos las definiciones básicas. Sea $\triangle ABC$ un triángulo no degenerado en el plano, sean $M_A$, $M_B$ y $M_C$ los puntos medios de los lados $BC$, $AC$ y $AB$, respectivamente, y sean $s_A$, $s_B$ y $s_C$ las mediatrices de los lados $BC$, $AC$ y $AB$. Formalmente, $s_A$ es la perpendicular a la recta $BC$ trazada por el punto $M_A$; las rectas $s_B$ y $s_C$ se definen de manera similar. Por geometría elemental, se sabe que las rectas $s_A$, $s_B$ y $s_C$ se intersecan en un único punto $O$. El punto $O$ tiene una propiedad notable: equidista de los tres vértices $A$, $B$ y $C$. La circunferencia centrada en $O$ con radio $OA$ se llama circunferencia circunscrita del triángulo $ABC$, y es la única circunferencia en el plano que pasa por los tres vértices del triángulo. El punto $O$ se conoce como el circuncentro del triángulo $ABC$.

Sean $H_A$, $H_B$ y $H_C$ las proyecciones ortogonales de los vértices $A$, $B$ y $C$ sobre las rectas $BC$, $AC$ y $AB$, respectivamente. Los segmentos $AH_A$, $BH_B$ y $CH_C$ se llaman las alturas del triángulo $ABC$. Por geometría elemental, se sabe que las rectas $AH_A$, $BH_B$ y $CH_C$ se intersecan en un único punto $H$, llamado el ortocentro del triángulo $ABC$. En un triángulo acutángulo o rectángulo, $H$ se encuentra sobre las propias alturas, mientras que en un triángulo obtusángulo se encuentra sobre sus prolongaciones.

Los segmentos $AM_A$, $BM_B$ y $CM_C$ se llaman las medianas del triángulo. Por geometría elemental, se sabe que las medianas se intersecan en un único punto $G$, llamado el centroide o baricentro del triángulo $ABC$. El triángulo $M_A M_B M_C$ se llama el triángulo medial del triángulo $ABC$. Los conceptos anteriores también se aplican a él: así, el punto $G$ es el baricentro del triángulo medial, y $O$ es el ortocentro del triángulo medial. La circunferencia circunscrita del triángulo $M_A M_B M_C$ pasa por $M_A$, $M_B$, $M_C$, $H_A$, $H_B$, $H_C$, así como por los puntos medios de los segmentos $AH$, $BH$, $CH$, razón por la cual se llama la circunferencia de los nueve puntos del triángulo $ABC$, y su centro se denota como $O_9$.

En un triángulo equilátero, los puntos $O$, $H$, $G$ y $O_9$ coinciden. En cualquier otro triángulo, son distintos dos a dos, pero yacen sobre una misma recta, llamada la recta de Euler del triángulo $ABC$. La disposición de estos cuatro puntos en la recta de Euler también es conocida: $O_9$ es siempre el punto medio del segmento $OH$, y el punto $G$ yace en el segmento $OH$ y lo divide en la razón $2 : 1$ (estando $G$ el doble de cerca de $O$ que de $H$).

Se requiere construir un triángulo no degenerado $ABC$ con vértices en puntos enteros, tal que $O$, $H$, $G$ y $O_9$ yagan sobre la recta dada, o informar que esto es imposible.

Entrada

La primera línea contiene un entero $t$, el número de casos de prueba ($1 \le t \le 5 \cdot 10^5$).

En la única línea de la descripción de cada caso de prueba, hay tres enteros, $k$, $\ell$ y $m$, que denotan los coeficientes de la recta ($-10^3 \le k, \ell, m \le 10^3$). La recta se definirá como el conjunto de puntos $(x, y)$ que satisfacen la ecuación $kx + \ell y + m = 0$. Se garantiza que $k^2 + \ell^2 > 0$.

Salida

Para cada caso de prueba, imprime seis enteros $A_x, A_y, B_x, B_y, C_x, C_y$, que denotan las coordenadas de los vértices de un triángulo no degenerado. Se deben satisfacer las condiciones $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$. La recta de Euler del triángulo $ABC$ debe tener la ecuación $kx + \ell y + m = 0$. Si dicho triángulo no existe, imprime seis ceros separados por espacios.

En cada una de las pruebas proporcionadas por el jurado, se garantiza que si existe al menos un triángulo $ABC$ con vértices enteros con la recta de Euler dada, también existe un triángulo que satisface las condiciones $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$.

Ejemplo

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

Nota

No exigimos explícitamente que $\triangle ABC$ sea no equilátero porque es imposible construir un triángulo equilátero cuyos vértices tengan coordenadas enteras.