M. Meteor Shower
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Colin hears that there will be a meteor shower in a few days. Being a romantic boyfriend, he plans to take Eva to watch it.

We model the situation on a two-dimensional plane. The Earth is a circle centered at the origin $$$O$$$ with radius $$$r$$$; its surface consists of the points satisfying $$$x^2+y^2=r^2$$$.

The meteor shower contains $$$n$$$ meteors. Meteor $$$i$$$ appears at the point $$$(x_i,y_i)$$$ and then moves continuously along the ray starting at this point in the direction of the nonzero vector $$$(dx_i,dy_i)$$$. It keeps moving in this direction unless it collides with the Earth. Meteors do not collide with one another, so their movements are independent.

Illustration of the example.

For a meteor that never collides with the Earth, the optimal observation site is the point on the Earth's surface with minimum distance to the meteor's trajectory ray. If a meteor does collide with the Earth—touching the surface counts as a collision—Colin instead wants the first point at which it reaches the surface.

For every meteor, determine which case occurs:

  • If it collides with the Earth, output "Crash at $$$(x,y)$$$", where $$$(x,y)$$$ is its first collision point.
  • Otherwise, output "Observe at $$$(x,y)$$$", where $$$(x,y)$$$ is the optimal observation site.

Print every coordinate with exactly four digits after the decimal point.

Input

The first line contains two integers $$$n$$$ and $$$r$$$ ($$$1\le n\le 10^5$$$, $$$1\le r\le 10^9$$$): the number of meteors and the radius of the Earth.

Each of the next $$$n$$$ lines contains four integers $$$x_i$$$, $$$y_i$$$, $$$dx_i$$$, and $$$dy_i$$$ ($$$-10^9\le x_i,y_i,dx_i,dy_i\le 10^9$$$). The pair $$$(x_i,y_i)$$$ is meteor $$$i$$$'s starting point, and $$$(dx_i,dy_i)$$$ is its direction vector. It is guaranteed that $$$(dx_i,dy_i)\ne(0,0)$$$.

It is also guaranteed that the distance from $$$O$$$ to every meteor's starting point is at least $$$r+0.1$$$.

Output

Output $$$n$$$ lines. Line $$$i$$$ must have one of the following forms:

  • "Crash at $$$(x,y)$$$" if meteor $$$i$$$ collides with the Earth, where $$$(x,y)$$$ is its first collision point;
  • "Observe at $$$(x,y)$$$" otherwise, where $$$(x,y)$$$ is the optimal observation site.

Do not print the quotation marks. Print both coordinates with exactly four digits after the decimal point. A coordinate is accepted if its absolute error from the jury answer does not exceed $$$10^{-3}$$$.

Example
Input
5 1
1 1 -1 0
2 2 -1 -1
2 1 -1 -1
2 3 -1 0
-1 -1 -1 -1
Output
Crash at (0.0000,1.0000)
Crash at (0.7071,0.7071)
Crash at (1.0000,0.0000)
Observe at (0.0000,1.0000)
Observe at (-0.7071,-0.7071)
Note

The answers for the example are illustrated in the figure in the statement.