Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Harry Potter and the Golden Snitch

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBrothers Fred and George Weasley once got into the sporting goods store and opened a box of Quidditch balls. After long and painful experiments they found out that the Golden Snitch is not enchanted at all. It is simply a programmed device. It always moves along the same trajectory, which is a polyline with vertices at the points (*x*_{0}, *y*_{0}, *z*_{0}), (*x*_{1}, *y*_{1}, *z*_{1}), ..., (*x*_{n}, *y*_{n}, *z*_{n}). At the beginning of the game the snitch is positioned at the point (*x*_{0}, *y*_{0}, *z*_{0}), and then moves along the polyline at the constant speed *v*_{s}. The twins have not yet found out how the snitch behaves then. Nevertheless, they hope that the retrieved information will help Harry Potter and his team in the upcoming match against Slytherin. Harry Potter learned that at the beginning the game he will be at the point (*P*_{x}, *P*_{y}, *P*_{z}) and his super fast Nimbus 2011 broom allows him to move at the constant speed *v*_{p} in any direction or remain idle. *v*_{p} is not less than the speed of the snitch *v*_{s}. Harry Potter, of course, wants to catch the snitch as soon as possible. Or, if catching the snitch while it is moving along the polyline is impossible, he wants to hurry the Weasley brothers with their experiments. Harry Potter catches the snitch at the time when they are at the same point. Help Harry.

Input

The first line contains a single integer *n* (1 ≤ *n* ≤ 10000). The following *n* + 1 lines contain the coordinates *x*_{i}, *y*_{i}, *z*_{i}, separated by single spaces. The coordinates of any two consecutive points do not coincide. The next line contains the velocities *v*_{p} and *v*_{s}, the last line contains *P*_{x}, *P*_{y}, *P*_{z}, separated by single spaces. All the numbers in the input are integers, their absolute value does not exceed 10^{4}. The speeds are strictly positive. It is guaranteed that *v*_{s} ≤ *v*_{p}.

Output

If Harry Potter can catch the snitch while it is moving along the polyline (including the end (*x*_{n}, *y*_{n}, *z*_{n})), print "YES" in the first line (without the quotes). Print in the second line *t*, which is the earliest moment of time, when Harry will be able to catch the snitch. On the third line print three numbers *X*, *Y*, *Z*, the coordinates of the point at which this happens. The absolute or relative error in the answer should not exceed 10^{ - 6}. If Harry is not able to catch the snitch during its moving along the described polyline, print "NO".

Examples

Input

4

0 0 0

0 10 0

10 10 0

10 0 0

0 0 0

1 1

5 5 25

Output

YES

25.5000000000

10.0000000000 4.5000000000 0.0000000000

Input

4

0 0 0

0 10 0

10 10 0

10 0 0

0 0 0

1 1

5 5 50

Output

NO

Input

1

1 2 3

4 5 6

20 10

1 2 3

Output

YES

0.0000000000

1.0000000000 2.0000000000 3.0000000000

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 10:49:31 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|