문제 설명

평면 위의 직선이 주어질 때, 꼭짓점이 정수 점에 위치하고 그 오일러 직선이 주어진 직선과 일치하는 삼각형을 구성하세요.

기본적인 정의를 떠올려 봅시다. $\triangle ABC$를 평면 위의 비퇴화 삼각형이라 하고, $M_A$, $M_B$, $M_C$를 각각 변 $BC$, $AC$, $AB$의 중점, $s_A$, $s_B$, $s_C$를 각각 변 $BC$, $AC$, $AB$의 수직이등분선이라 합시다. 공식적으로 $s_A$는 점 $M_A$를 지나며 직선 $BC$에 수직인 직선이고, 직선 $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$)이 주어집니다. 이 직선은 방정식 $kx + \ell y + m = 0$을 만족하는 점 $(x, y)$들의 집합으로 정의됩니다. $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$을 가져야 합니다. 그러한 삼각형이 존재하지 않으면 공백으로 구분된 여섯 개의 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$가 정삼각형이 아니어야 한다는 조건을 명시적으로 요구하지 않습니다.