#jag2018summerday2g. [jag2018summer_day2_g]Construct One Point

[jag2018summer_day2_g]Construct One Point

Problem Statement

You have QQ triangles, numbered 11 through QQ.

The coordinates of the vertices of the ii-th triangle are (xi1,yi1)(x_{i1}, y_{i1}), (xi2,yi2)(x_{i2}, y_{i2}) and (xi3,yi3)(x_{i3}, y_{i3}) in counterclockwise order. Here, xi1x_{i1}, xi2x_{i2}, xi3x_{i3}, yi1y_{i1}, yi2y_{i2} and yi3y_{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.
  • 1leqQleq101 \\leq Q \\leq 10 000000
  • 0leqxi1,xi2,xi3,yi1,yi2,yi3leq1090 \\leq x_{i1}, x_{i2}, x_{i3}, y_{i1}, y_{i2}, y_{i3} \\leq 10^9
  • (xi1,yi1)(x_{i1}, y_{i1}), (xi2,yi2)(x_{i2}, y_{i2}) and (xi3,yi3)(x_{i3}, y_{i3}) are in counterclockwise order.
  • The areas of the triangles are not 00.

Input

Input is given from Standard Input in the following format:

QQ x11x_{11} y11y_{11} x12x_{12} y12y_{12} x13x_{13} y13y_{13} x21x_{21} y21y_{21} x22x_{22} y22y_{22} x23x_{23} y23y_{23} :: xQ1x_{Q1} yQ1y_{Q1} xQ2x_{Q2} yQ2y_{Q2} xQ3x_{Q3} yQ3y_{Q3}

Output

Output should contain QQ lines.

In the ii-th line, if there is no grid point contained in the interior (excluding the boundary) of the ii-th triangle, print -1 -1. If it exists, choose one such grid point, then print its xx-coordinate and yy-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