Flatland Fidget Spinner

Given the pixel colors a camera recorded of a three-armed spinner, recover the camera's position and rotation angle.

Hard8GeometryBinary searchImplementationMathNo attempts yetTime limit2sMemory limit512 MB

Problem

Freddy the Flatland photographer wants to write about new toys for the newspaper Flatland Financial Times. He saw a very nice picture of a fidget spinner in the magazine Flatland Weekly, and he likes it so much that he wants to publish the same picture. Flatland copyright law forbids copying the picture, so Freddy decides to take his own picture that looks exactly the same. Help him place his camera.

A fidget spinner

Photography in Flatland

Freddy owns one 1MP camera and a few cheaper cameras with fewer pixels. One pixel records three real numbers (R,G,B)(R, G, B) between 00 and 11 as a colour. In the picture Freddy wants to reproduce, the fidget spinner lies on a fully black (0,0,0)(0, 0, 0) background. Fully black pixels make up at most 40%40\% of the picture. The spinner is never cut off, so the leftmost pixel and the rightmost pixel are always fully black. The arms of the spinner have pure colours, in counter clockwise order red (1,0,0)(1, 0, 0), green (0,1,0)(0, 1, 0) and blue (0,0,1)(0, 0, 1). Every arm has length 11, and two neighbouring arms are separated by the same angle 2π/32\pi/3, that is 120120 degrees. The spinner stands in the Origin Photography Studio with its middle at x=0x = 0, y=0y = 0 and the tip of its blue arm at x=1x = -1, y=0y = 0.

A camera setup in Flatland and the picture it produces

A camera with nn pixels and viewing angle θ\theta captures the angle θ\theta in total, so one pixel covers the angle θ/n\theta/n. The camera sits at position (x,y)(x, y), and the angle α\alpha is the counter clockwise angle between the positive xx-axis and the centre of the camera view. The colour of a pixel is the average over the angular range that the pixel covers. Each arm adds its own colour in proportion to the part of that range where the arm is the object closest to the camera. Arms hide each other. Where two arms overlap in the same direction, only the one nearer to the camera is recorded.

The camera in the figure above has n=8n = 8 pixels and a viewing angle of θ=80\theta = 80 degrees, so one pixel covers 1010 degrees. One pixel of that picture contains both the red arm and the blue arm. Inside that pixel blue covers 66 degrees and red covers 44 degrees, so the pixel records the colour 410(1,0,0)+610(0,0,1)=(0.4,0.0,0.6)\frac{4}{10} \cdot (1, 0, 0) + \frac{6}{10} \cdot (0, 0, 1) = (0.4, 0.0, 0.6), a shade of purple.

Input

The first line contains the camera properties: the number of pixels nn (8n1068 \le n \le 10^6) and the viewing angle θ\theta (2π/8θ2π/42\pi/8 \le \theta \le 2\pi/4) in radians.

Each of the next nn lines contains three real numbers RR, GG and BB (0R,G,B10 \le R, G, B \le 1) with R+G+B1+1010R + G + B \le 1 + 10^{-10}. The pixels are given in clockwise order. Every real number in the input has at most 1010 digits after the decimal point.

Output

Print xx, yy and α\alpha (0α<2π0 \le \alpha < 2\pi), the position of the camera and its rotation in radians, separated by single spaces. Print all three numbers with exactly four digits after the decimal point.

Exactly one camera placement produces the given picture, and each of the three printed values stays far from a rounding boundary, so the answer is unique.