G - Construct One Point Editorial /

Time Limit: 2 sec / Memory Limit: 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