你有 $Q$ 个三角形，编号为 $1$ 到 $Q$。

第 $i$ 个三角形的顶点坐标为 $(x_{1_i}, y_{1_i})$、$(x_{2_i}, y_{2_i})$ 和 $(x_{3_i}, y_{3_i})$，按逆时针顺序给出。其中 $x_{1_i}, x_{2_i}, x_{3_i}, y_{1_i}, y_{2_i}, y_{3_i}$ 均为整数。

对于每个三角形，判断其内部（不包含边界）是否存在格点。如果存在，请构造出其中一个点。

输入格式

输入按以下格式给出：

$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}$ $\dots$ $x_{1_Q} \ y_{1_Q} \ x_{2_Q} \ y_{2_Q} \ x_{3_Q} \ y_{3_Q}$

数据范围

所有输入值均为整数，$1 \le Q \le 10\,000$，$0 \le x_{1_i}, x_{2_i}, x_{3_i}, y_{1_i}, y_{2_i}, y_{3_i} \le 10^9$，$(x_{1_i}, y_{1_i}), (x_{2_i}, y_{2_i})$ 和 $(x_{3_i}, y_{3_i})$ 按逆时针顺序排列，三角形为非退化三角形。

输出格式

输出应包含 $Q$ 行。

在第 $i$ 行中，如果三角形 $i$ 的内部（不包含边界）不存在格点，输出 “-1 -1”。如果存在，请选择其中一个格点，并输出其 $x$ 坐标和 $y$ 坐标，中间用空格隔开。

样例

输入 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