"Hit!" is a popular game in ancient Byteland.
The very first version of the game is quite simple: each player picks up a stone and throws it at a circle drawn on the ground. A player wins if his/her stone lands inside the circle.
After 20 years of practice, Bitman, a young man living in ancient Byteland, has mastered the skill of throwing stones – he can throw a stone at any specific place he wants. With such skill, Bitman plays "Hit!" without losing a single game. He simply targets every stone at the center of the circle!
The King of Hackerland hears the story of Bitman and wants to challenge him with a harder, though still very simple, version of "Hit!".
In each game, two circles which share a positive common area are drawn on the ground. In order to win, the player must throw a stone at the common area of the two circles.
As Bitman had no idea how to target his stone at the common area, he asks for your help. Given the coordinates of the centers and radii of the two circles, please tell Bitman the coordinates of any point he can target at such that he can win the game.
For simplicity, you can consider the landing position of the stone as a single point.
The input consists of two lines, each describes one circle drawn on the ground. Each line contains three *integers* x, y and r, denoting respectively the x-coordinate, y-coordinate, and the radius of a circle.
All coordinates have their absolute value no more than 100, and 1 ≤ r ≤ 100 for both circles.
Output two numbers, the x-coordinate and y-coordinate of a point where Bitman can throw his stone at to win the game.
Your answer will be accepted if for each of the two circles, the point lies inside the circle or that the distance between the point and the circle is not greater than 10 - 5.
In the first sample, (1.5, 2.5) is a possible answer as it lies inside the common area of two circles drawn. Please note that there exists more than one possible answer in this case. For example, (2, 2), (1, 2) and (2.1, 1.87) are also possible answers.
## Input
The input consists of two lines, each describes one circle drawn on the ground. Each line contains three *integers* x, y and r, denoting respectively the x-coordinate, y-coordinate, and the radius of a circle. All coordinates have their absolute value no more than 100, and 1 ≤ r ≤ 100 for both circles.
## Output
Output two numbers, the x-coordinate and y-coordinate of a point where Bitman can throw his stone at to win the game. Your answer will be accepted if for each of the two circles, the point lies inside the circle or that the distance between the point and the circle is not greater than 10 - 5.
[samples]
## Note
In the first sample, (1.5, 2.5) is a possible answer as it lies inside the common area of two circles drawn. Please note that there exists more than one possible answer in this case. For example, (2, 2), (1, 2) and (2.1, 1.87) are also possible answers.
Let $ C_1 = (x_1, y_1, r_1) $ and $ C_2 = (x_2, y_2, r_2) $ be the two circles, with centers at $ (x_1, y_1) $, $ (x_2, y_2) $ and radii $ r_1, r_2 > 0 $, respectively. Assume the circles intersect in a region of positive area.
**Objective**: Find a point $ (x, y) \in \mathbb{R}^2 $ such that:
$$
\sqrt{(x - x_1)^2 + (y - y_1)^2} \leq r_1 \quad \text{and} \quad \sqrt{(x - x_2)^2 + (y - y_2)^2} \leq r_2
$$
**Solution**: Let $ d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $. Since the circles have positive common area, $ d < r_1 + r_2 $ and $ d > |r_1 - r_2| $.
Let $ \vec{v} = (x_2 - x_1, y_2 - y_1) $. Define the unit vector $ \hat{v} = \frac{\vec{v}}{d} $.
Then, a point in the intersection is:
$$
(x, y) = \left( x_1 + \frac{r_1}{d} \cdot \frac{d + r_1 - r_2}{2},\ y_1 + \frac{r_1}{d} \cdot \frac{d + r_1 - r_2}{2} \cdot \frac{y_2 - y_1}{d} \right)
$$
Alternatively, simpler: the midpoint between the two centers lies in the intersection if $ d \leq \min(r_1, r_2) $, otherwise move from $ (x_1, y_1) $ toward $ (x_2, y_2) $ by distance $ \frac{r_1 + d - r_2}{2} $.
But to guarantee correctness and simplicity, output the point along the line segment between centers at distance $ r_1 $ from $ (x_1, y_1) $ toward $ (x_2, y_2) $, **clamped** to the intersection:
Let $ t = \frac{r_1}{d} \cdot \frac{d + r_1 - r_2}{2r_1} $? No — simpler:
Use:
$$
(x, y) = \left( x_1 + \frac{r_1 (x_2 - x_1)}{d} \cdot \frac{d + r_1 - r_2}{2r_1},\ y_1 + \frac{r_1 (y_2 - y_1)}{d} \cdot \frac{d + r_1 - r_2}{2r_1} \right)
$$
Actually, standard solution: the point lying on the line segment between centers at distance $ a = \frac{d^2 + r_1^2 - r_2^2}{2d} $ from $ (x_1, y_1) $:
Let $ a = \frac{d^2 + r_1^2 - r_2^2}{2d} $
Then:
$$
x = x_1 + \frac{a}{d} (x_2 - x_1), \quad y = y_1 + \frac{a}{d} (y_2 - y_1)
$$
This point lies on the line segment and is at distance $ a $ from $ C_1 $, and by construction lies inside both circles.
**Final Output**:
$$
x = x_1 + \frac{d^2 + r_1^2 - r_2^2}{2d^2} (x_2 - x_1), \quad y = y_1 + \frac{d^2 + r_1^2 - r_2^2}{2d^2} (y_2 - y_1)
$$