Description

Given a line on the plane, construct a triangle with vertices at integer points such that its Euler line coincides with the given line.

Recall the basic definitions. Let $\triangle ABC$ be a non-degenerate triangle on the plane, $M_A$, $M_B$, and $M_C$ be the midpoints of sides $BC$, $AC$, and $AB$, respectively, and $s_A$, $s_B$, and $s_C$ be the perpendicular bisectors to sides $BC$, $AC$, and $AB$. Formally, $s_A$ is the perpendicular to line $BC$, drawn at point $M_A$; lines $s_B$ and $s_C$ are defined similarly. From school geometry, it is known that lines $s_A$, $s_B$, and $s_C$ intersect at a single point $O$. The point $O$ has a remarkable property, namely, it is equidistant from all three vertices $A$, $B$, and $C$. The circle centered at $O$ with radius $OA$ is called the circumcircle of triangle $ABC$, and it is the unique circle in the plane that passes through all three vertices of the triangle. The point $O$ is referred to as the circumcenter of triangle $ABC$.

Let $H_A$, $H_B$, and $H_C$ denote the orthogonal projections of vertices $A$, $B$, and $C$ onto lines $BC$, $AC$, and $AB$, respectively. The segments $AH_A$, $BH_B$, and $CH_C$ are called the heights of triangle $ABC$. From school geometry, it is known that lines $AH_A$, $BH_B$, and $CH_C$ intersect at a single point $H$, called the orthocenter of triangle $ABC$. In an acute or right triangle, $H$ lies on the heights themselves, while in an obtuse triangle, it lies on their extensions.

The segments $AM_A$, $BM_B$, and $CM_C$ are called the medians of the triangle. From school geometry, it is known that the medians intersect at a single point $G$, called the centroid or barycenter of triangle $ABC$. The triangle $M_A M_B M_C$ is called the medial triangle for triangle $ABC$. The concepts above also apply to it: thus, point $G$ is the barycenter of the medial triangle, and $O$ is the orthocenter of the medial triangle. The circumcircle of triangle $M_A M_B M_C$ passes through $M_A$, $M_B$, $M_C$, $H_A$, $H_B$, $H_C$, as well as through the midpoints of segments $AH$, $BH$, $CH$, which is why it is called the nine-point circle of triangle $ABC$, and its center is denoted as $O_9$.

In an equilateral triangle, points $O$, $H$, $G$, and $O_9$ coincide. In any other triangle, they are pairwise distinct, but they lie on a single line, called the Euler line of triangle $ABC$. The arrangement of these four points on the Euler line is also known: $O_9$ is always the midpoint of segment $OH$, and point $G$ lies on segment $OH$ and divides it in the ratio $2 : 1$ (with $G$ being twice as close to $O$ as to $H$).

You are required to construct a non-degenerate triangle $ABC$ with vertices at integer points, such that $O$, $H$, $G$, and $O_9$ lie on the given line, or report that this is impossible.

Input

The first line contains an integer $t$, the number of test cases ($1 \le t \le 5 \cdot 10^5$).

In the only line of the test case description, there are three integers, $k$, $\ell$, and $m$, denoting the coefficients of the line ($-10^3 \le k, \ell, m \le 10^3$). The line will be defined as the set of points $(x, y)$ that satisfy the equation $kx + \ell y + m = 0$. It is guaranteed that $k^2 + \ell^2 > 0$.

Output

For each test case, output six integers $A_x, A_y, B_x, B_y, C_x, C_y$, denoting the coordinates of the vertices of a non-degenerate triangle. The conditions $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$ must be satisfied. The Euler line of triangle $ABC$ must have the equation $kx + \ell y + m = 0$. If such a triangle does not exist, output six zeros separated by spaces.

In each of the tests provided by the jury, it is guaranteed that, if there exists at least one triangle $ABC$ with integral vertices with the given Euler line, there is also a triangle with conditions $-10^6 \le A_x, A_y, B_x, B_y, C_x, C_y \le 10^6$ satisfied.

Example

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

We do not explicitly require $\triangle ABC$ to be non-equilateral because it is impossible to come up with an equilateral triangle whose vertices have integer coordinates.