/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
Score : 100 points
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
