D. Demon on the Grid
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

In a vast and mysterious world lies an infinite two-dimensional grid. Each location in this grid is identified by integer coordinates $$$(x, y)$$$. You have been informed that a demon is hiding somewhere in this grid, and your mission is to find the exact position of the demon before it disappears forever.

You have received $$$n$$$ clues from ancient observers who tried to track the demon's movement. Each clue is described by three integers $$$(x_i, y_i, d_i)$$$, meaning that the demon is at a Cartesian distance of $$$\sqrt{d_i}$$$ from the point $$$(x_i, y_i)$$$. However, the demon is a master of illusions, so not all clues can be trusted. The demon has created shadow replicas of itself at certain locations, causing some clues to be either real or fake followed by these conditions: if a clue is real, the demon's actual position must exactly match the distance indicated by that clue's coordinates and distance value; if a clue is fake, the demon's position must not match that distance.

Unfortunately, you do not know which clues are real and which are fake. To ensure that the demon can be captured, you have to find the maximum number of real clues that allows you to locate the demon's position without needing to know in advance which clues are real.

Formally, let $$$c_i$$$ represent clue $$$(x_i,y_i,d_i)$$$. Suppose the demon is located at position $$$o = (o_x,o_y)$$$, the reality of a clue is defined as follows:

  • A clue $$$c_i$$$ is real if and only if $$$(o_x - x_i)^2 + (o_y - y_i)^2 = d_i$$$.
  • A clue $$$c_i$$$ is fake if and only if $$$(o_x - x_i)^2 + (o_y - y_i)^2 \neq d_i$$$.
You are given a set $$$S = \{c_1,c_2,...,c_n\}$$$. You need to find the maximum integer $$$k$$$ and a position $$$p \in \mathbb{Z} \times \mathbb{Z}$$$ such that:
  • There is exactly one $$$T \subseteq S$$$ of size $$$k$$$ that makes $$$p$$$ a unique valid solution for $$$T$$$.
  • A position $$$p$$$ is a unique valid solution for a set $$$T$$$ if and only if there is only $$$p$$$ that is a valid solution for $$$T$$$ (i.e., $$$p$$$ is a valid solution for $$$T$$$, and for all $$$q \in \mathbb{Z} \times \mathbb{Z} - \{ p \}$$$, $$$q$$$ is not a valid solution for $$$T$$$).
  • A position $$$p$$$ is a valid solution for a set $$$T$$$ if and only if every clue $$$c \in T$$$ is real, and every clue $$$c^\prime \notin T$$$ is fake, given that the demon is located at position $$$p$$$.
Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$

The next $$$n$$$ lines contain clues. Each contains three integers $$$x_i, y_i, d_i$$$ $$$(-10^5 \leq x_i, y_i \leq 10^5, 1 \leq d_i\leq 10^5)$$$

It is guaranteed that the demon's coordinates must be integers.

Output

If no solution exists, print -1.

Otherwise, print two lines. On the first line, print the maximum number $$$k$$$ of real clues that satisfy the conditions. On the second line, print two space-separated integers representing the demon's position: $$$o_x$$$ and $$$o_y$$$.

Examples
Input
4
15 0 9
21 0 9
2 0 13
8 0 13
Output
2
18 0
Input
8
0 0 25
0 10 25
5 5 25
20 0 25
20 10 25
25 5 25
10 -10 16
18 -10 16
Output
-1
Input
8
0 0 25
1 0 16
2 0 9
10 0 9
16 0 9
-12 0 25
-11 0 16
-10 0 9
Output
2
13 0
Note

In the first test case:

if $$$k = 4:$$$ The only possible set includes all four clues, and this set is contradictory.

if $$$k = 3:$$$ There are four possible sets of three clues, and all of them are contradictory.

if $$$k = 2:$$$

  • Choosing clues $$$1$$$ and $$$2$$$ as real clues uniquely locates the demon's position at $$$(18, 0)$$$.
  • Choosing clues $$$3$$$ and $$$4$$$ leads to two possible positions, $$$(5, 2)$$$ and $$$(5, -2)$$$, so the demon's location cannot be uniquely determined.
  • All other pairs of clues are contradictory.
  • Therefore, {$$$1, 2$$$} is the only set of two clues that uniquely determines the demon's position.

if $$$k = 1:$$$ Choosing any single clue is ambiguous, resulting in multiple solutions.

Therefore, the maximum number of clues that satisfy the conditions is $$$2$$$, and the corresponding demon position is $$$(18, 0)$$$.

In the second test case:

If $$$k \ge 4$$$: It is easy to see that there is no way to choose $$$k$$$ clues such that they determine a position.

if $$$k = 3$$$: There are two possible ways to select three clues that determines a position

  • Choosing clue $$$1,2,3$$$ leads to the position $$$(0,5)$$$.
  • Choosing clue $$$4,5,6$$$ leads to the position $$$(20,5)$$$.
  • Thus, $$$k = 3$$$ is invalid because there is more than one possible way to choose $$$k$$$ clues that determine a position.

if $$$k = 2$$$: There are five possible ways to select two clues that determine a position:

  • Choosing clue $$$1,3$$$ leads to the position $$$(5,0)$$$.
  • Choosing clue $$$2,3$$$ leads to the position $$$(5,10)$$$.
  • Choosing clue $$$4,6$$$ leads to the position $$$(25,0)$$$.
  • Choosing clue $$$5,6$$$ leads to the position $$$(25,10)$$$.
  • Choosing clue $$$7,8$$$ leads to the position $$$(14,-10)$$$.
  • Therefore, $$$k = 2$$$ is also invalid.

if $$$k = 1$$$: Choosing any single clue is ambiguous, resulting in multiple solutions.

Therefore, the result is $$$-1$$$.