Описание

По данной прямой на плоскости постройте треугольник с вершинами в целых точках, прямая Эйлера которого совпадает с данной прямой.

Напомним основные определения. Пусть $\triangle ABC$ — невырожденный треугольник на плоскости, $M_A$, $M_B$ и $M_C$ — середины сторон $BC$, $AC$ и $AB$ соответственно, а $s_A$, $s_B$ и $s_C$ — серединные перпендикуляры к сторонам $BC$, $AC$ и $AB$. Формально, $s_A$ — это перпендикуляр к прямой $BC$, проведённый в точке $M_A$; прямые $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$ и делит его в отношении $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$). Прямая определяется как множество точек $(x, y)$, удовлетворяющих уравнению $kx + \ell y + m = 0$. Гарантируется, что $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$ не был равносторонним, поскольку невозможно придумать равносторонний треугольник, вершины которого имеют целые координаты.