Problem Statement

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

The coordinates of the vertices of the $i$-th triangle are $(x_{i1}, y_{i1})$, $(x_{i2}, y_{i2})$ and $(x_{i3}, y_{i3})$ in counterclockwise order. Here, $x_{i1}$, $x_{i2}$, $x_{i3}$, $y_{i1}$, $y_{i2}$ and $y_{i3}$ 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.

Constraints

• All input values are integers.
• $1 \\leq Q \\leq 10$ $000$
• $0 \\leq x_{i1}, x_{i2}, x_{i3}, y_{i1}, y_{i2}, y_{i3} \\leq 10^9$
• $(x_{i1}, y_{i1})$, $(x_{i2}, y_{i2})$ and $(x_{i3}, y_{i3})$ are in counterclockwise order.
• The areas of the triangles are not $0$.

Input

Input is given from Standard Input in the following format:

$Q$ $x_{11}$ $y_{11}$ $x_{12}$ $y_{12}$ $x_{13}$ $y_{13}$ $x_{21}$ $y_{21}$ $x_{22}$ $y_{22}$ $x_{23}$ $y_{23}$ $:$ $x_{Q1}$ $y_{Q1}$ $x_{Q2}$ $y_{Q2}$ $x_{Q3}$ $y_{Q3}$

Output

Output should contain $Q$ lines.

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

Sample Input 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

Sample Output 1

3 6
2 3
-1 -1
10 4