시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 2 2 2 100.000%

문제

You have $Q$ triangles, numbered $1$ through $Q$.

The coordinates of the vertices of the $i$-th triangle are $(x_{1_i}, y_{1_i})$, $(x_{2_i}, y_{2_i})$ and $(x_{3_i}, y_{3_i})$ in counterclockwise order. Here, $x_{1_i}$, $x_{2_i}$, $x_{3_i}$, $y_{1_i}$, $y_{2_i}$ and $y_{3_i}$ are all integers.

For each triangle, determine if there exists a grid point contained in its interior (excluding the boundary). If it exists, construct one such point.

입력

Input is given in the following format:

$Q$

$x_{1_1}$ $y_{1_1}$ $x_{2_1}$ $y_{2_1}$ $x_{3_1}$ $y_{3_1}$

$x_{1_2}$ $y_{1_2}$ $x_{2_2}$ $y_{2_2}$ $x_{3_2}$ $y_{3_2}$

$\ldots$

$x_{1_Q}$ $y_{1_Q}$ $x_{2_Q}$ $y_{2_Q}$ $x_{3_Q}$ $y_{3_Q}$

출력

Output should contain $Q$ lines.

In the $i$-th line, if there is no grid point contained in the interior (excluding the boundary) of Triangle $i$, print "-1 -1". If it exists, choose one such grid point, then print its $x$-coordinate and $y$-coordinate with a space in between.

제한

All input values are integers, $1 \leq Q \leq 10\,000$, $0 \leq x_{1_i}, x_{2_i}, x_{3_i}, y_{1_i}, y_{2_i}, y_{3_i} \leq 10^9$, $(x_{1_i}, y_{1_i})$, $(x_{2_i}, y_{2_i})$ and $(x_{3_i}, y_{3_i})$ are listed in counterclockwise order, the triangles are non-degenerate.

예제 입력 1

4
1 7 3 5 5 7
1 4 1 2 5 4
6 1 7 1 7 6
11 3 11 4 8 5

예제 출력 1

3 6
2 3
-1 -1
10 4