OpenKattis
Purdue University

Within Arm's Reach

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?

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$ $1\, 000$ Length of the $i$th segment $-20\, 000$ $\leq$ $x, y$ $\leq$ $20\, 000$ 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

Sample Input 1 Sample Output 1
3
5
3
4
5 3

4.114 -2.842
6.297 -0.784
5.000 3.000

Sample Input 2 Sample Output 2
2
4
2
-8 -3

-3.745 -1.404
-5.618 -2.107