Description:
You are given $$$n$$$ circles on the plane. The $$$i$$$-th of these circles is given by a tuple of integers $$$(x_i, y_i, r_i)$$$, where $$$(x_i, y_i)$$$ are the coordinates of its center, and $$$r_i$$$ is the radius of the circle.
Please find a circle $$$C$$$ which meets the following conditions:
- $$$C$$$ is contained inside all $$$n$$$ circles given in the input.
- Among all circles $$$C$$$ that meet the first condition, the radius of the circle is maximum.
Let the largest suitable circle have the radius of $$$a$$$.
Your output $$$C$$$, described as $$$(x,y,r)$$$, will be accepted if it meets the following conditions:
- For each $$$i$$$, $$$\sqrt{(x_i-x)^2+(y_i-y)^2}+ r \le r_i+\max(a,1)\cdot 10^{-7}$$$.
- The absolute or relative error of $$$r$$$ does not exceed $$$10^{-7}$$$. Formally, your answer is accepted if and only if $$$\frac{\left|r - a\right|}{\max(1, a)} \le 10^{-7}$$$.
Input Format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of circles.
The $$$i$$$-th of the following $$$n$$$ lines contains three integers $$$x_i$$$, $$$y_i$$$, $$$r_i$$$ ($$$-10^6 \le x_i,y_i \le 10^6$$$, $$$1 \le r_i \le 2 \cdot 10^6$$$).
It is guaranteed that there is a circle with a radius of at least $$$10^{-6}$$$ which is contained inside all $$$n$$$ circles.
Output Format:
Output three real values, $$$x$$$, $$$y$$$, and $$$r$$$ — the coordinates of the center and the radius of the circle.
Note:
A two-dimensional plot depicting the first test case is given below. The output circle $$$C$$$ is dashed with blue lines.
A two-dimensional plot depicting the second test case is given below. The output circle $$$C$$$ is dashed with blue lines.