João wants to join the robotic football team of his university. However, since he knows little about robotics and mathematics, he decided to build a $2$-dimensional robotic arm to bootstrap his knowledge.

The robotic arm is composed of $N$ segments of various lengths. The segments can form any angle between them, including configurations that make it appear to self-intersect when viewed from above. The robotic arm works great, but it is not trivial to position the arm’s tip as close as possible to given $x$, $y$ target coordinates with so many joints to control. Can you help João?

-----Task-----
Given the robotic arm description and target coordinates relative to the arm’s origin, calculate a configuration that places the arm’s tip as close as possible to the target.

-----Input-----
The first line contains $N$, the number of segments composing the robotic arm. $N$ lines follow, each with an integer $L_ i$ describing the length of the $i$th segment from the fixed point until the arm’s tip. There is one more line with $2$ integers: the $x$, $y$ coordinates of the target point to reach.

-----Constraints-----

$1$

$\leq $

$N$

$\leq $

$20$

Number of segments in the robotic arm

$1$

$\leq $

$L_ i$

$\leq $

$1000$

Length of the $i$th segment

$-20000$

$\leq $

$x, y$

$\leq $

$20000$

Target coordinates to attempt to reach

-----Output-----
The output should contain $N$ lines, each containing two real numbers $x_ i$, $y_ i$ indicating the coordinates of the tip of the $i$th segment.

The length of the $i$th segment computed from the solution and input $L_ i$ may not differ by more than $0.01$. Similarly, the absolute error between the solution’s distance to the target and the minimum possible distance to the target cannot exceed $0.01$.

Note that, in general, there are many solutions. Your program may output any of them.

-----Explanation for Sample Input 1-----
Sample output 1 corresponds to the drawing on the left:



The drawing on the right corresponds to the following, equally acceptable output for sample input 1:

3.923 3.100
1.118 2.037
5.000 3.000


-----Explanation for Sample Input 2-----

-----Examples-----
Sample Input:
3
5
3
4
5 3
Sample Output:
4.114 -2.842
6.297 -0.784
5.000 3.000

Difficulty: competition

Starter code:

Solutions: