• 来源：Petrozavodsk Winter Training Camp 2018，Day 3: AtCoder Contest，Problem C
• 原题名：Construct Point
• 时间限制：2 秒
• 空间限制：256 MiB

题目描述

几何社的 Mira 正在整理一批三角形图纸。每张图纸给出一个三角形的三个顶点，顶点坐标都是整数，并且三个顶点按逆时针顺序给出。

对于每个三角形，她想知道：是否存在一个整点严格位于这个三角形内部？

这里整点指横坐标和纵坐标都是整数的点；严格位于内部表示不能在三角形边界上。

如果存在，请构造任意一个这样的整点；如果不存在，请输出 -1 -1。

输入格式

第一行包含一个整数 $Q$，表示三角形数量。

接下来 $Q$ 行，第 $i$ 行包含六个整数

$$x_{1i},y_{1i},x_{2i},y_{2i},x_{3i},y_{3i},$$

表示第 $i$ 个三角形的三个顶点

$$(x_{1i},y_{1i}),\ (x_{2i},y_{2i}),\ (x_{3i},y_{3i}).$$

三个顶点按逆时针顺序给出。

输出格式

输出 $Q$ 行。

对于第 $i$ 个三角形：

• 如果不存在严格位于其内部的整点，输出 -1 -1；
• 否则输出两个整数 $x,y$，表示一个严格位于其内部的整点坐标。

如果存在多个答案，输出任意一个即可。

数据范围

• $1\le Q\le 10000$；
• $0\le x_{1i},x_{2i},x_{3i},y_{1i},y_{2i},y_{3i}\le 10^9$；
• 三个顶点按逆时针顺序给出；
• 输入的三角形均非退化。

样例

输入

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

输出

3 6
2 3
-1 -1
10 4