AT_jag2018summer_day2_g Construct One Point

[problemUrl]: https://atcoder.jp/contests/jag2018summer-day2/tasks/jag2018summer_day2_g 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.

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 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.

### 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 $. ### Sample Explanation 1 !\[\](https://img.atcoder.jp/cookie/d5f2f1c2e6c3476fedb40cdc9fc1403f.png)