Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
68 - ZOJ Monthly, July 2008 - 1003
Final Treasure

Time Limit: 2 Seconds      Memory Limit: 65536 KB

The final treasure is about a necklace. And why it is the final one? Because it is the very necklace that Zeus gave it to Hera as a birthday present. What does the necklace look like? You can treat it as a tree, which is made of valuable diamonds. To simplify the problem, mass of the string which between two diamonds can be regarded as 0, and mass of each diamond is 1. And now, it is hanging on the wall in the world's biggest temple. So now the problem is: what is the coordinate of a given diamond?

Each string between two diamonds has a length of 1, and diamond No.0 and No.(N - 1) are the only two points fixed on the wall, they both have equal heights. Diamond No.0's coordinate is (0,0). Now give you the distance between diamond No.0 and No.(N - 1), your task is to calculate the coordinate of diamond No.K.

Input

The input contains multiple test cases!
Each test case starts with a line containing three numbers N, S, K (3 <= N <= 200 , 0 <= K <= (N - 1)) separated by a space. Here N and K are integers, S is a real number. Then the following (N - 1) lines each contains one number, number Ei in line i(2 <= i <= N) which means there is a string between diamond No.(i - 2) and diamond No.Ei. We guarantee that diamond No.0 and No.(N - 1) are leaves, and S is a valid real number.

Output

Each line contains two numbers X, Y (must be rounded off to 3 decimal places), represent the coordinate of the diamond No.K.

Sample Input

3 1 1
1
2
10 2 6
1
2
9

1
1
3
2
6
7

Sample Output

0.500 -0.866
1.500 -1.866

Author: FAN, Yuzhe


Submit    Status