问题描述

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

第 $i$ 个三角形的顶点坐标按逆时针顺序排列为 $(x_{i1}, y_{i1})$，$(x_{i2}, y_{i2})$ 和 $(x_{i3}, y_{i3})$。其中，$x_{i1}$，$x_{i2}$，$x_{i3}$，$y_{i1}$，$y_{i2}$ 和 $y_{i3}$ 都是整数。

对于每个三角形，判断其内部（不包括边界）是否存在一个网格点。如果存在，则构造一个这样的点。

约束条件

• 所有输入值都是整数。
• $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})$ 和 $(x_{i3}, y_{i3})$ 按逆时针顺序排列。
• 三角形的面积不为 $0$。

输入

输入以以下格式从标准输入给出：

$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}$

输出

输出应包含 $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