Before the cycling race, there is an artistic preshow that takes place on the circular track that is a spectacle for the eyes.

The preshow has ~N~ seconds labelled by ~1,2,3, \ldots N~. In each second a new cyclist joins the show at an initial position on the track at ~(x_i, y_i)~. The cyclist will then cycle around the track until the end of the show. Each cyclist cycles in a circle around ~(0,0)~, either clockwise or anti-clockwise. Each cyclist has differing speeds, each taking ~s_i~ seconds to complete a full revolution. The cyclists are experts at avoiding each other, so there is no need to worry about them colliding with each other, even if their positions are the same. In fact, whenever a new cyclist joins in, their starting position will not be occupied by previous cyclists.

The above image shows the paths of the first 3 cyclists in the first sample input. The first cyclist joins at ~(1,0)~ at ~t = 1~ and takes 3 seconds to make a full anticlockwise rotation. That means, at ~t = 2~, they are at the position ~(-0.5, 0.866)~, and have rotated 120 degrees anticlockwise relative to the origin. In comparison, the third cyclist joins at ~t = 3~ and takes 6 seconds to make a clockwise rotation. At ~t = 4~, they are at ~(1.732,1)~ and have rotated 60 degrees clockwise relative to the origin.

For the sake of vfx (which stands for visual effects), immediately after the ~i~th cyclist has joined, a new convex polygon is projected onto the track. This convex polygon must contain every cyclist on its interior or edge. After each cyclist has joined, what is the smallest area of the convex polygon which can be projected?

The above image shows the positions of the cyclists at ~t = 5~ in the first sample input. The smallest convex polygon such that all cyclists are on the interior is also shown.

Input

The first line has 1 integer, ~N~ (~1 \le N \le 5 \times 10^4~), the number of seconds in the show, and the number of cyclists that join. ~N~ lines follow, each describing the cyclist that joins at the ~i~th second. Each line has 4 integers, ~x_i, y_i, d_i, s_i~

• ~x_i, y_i~ (~-10^9 \le x_i, y_i \le 10^9~) is the initial position of the cyclist
• ~d_i~ is either 0 or 1. If ~d_i~ is 0 then they are cycling counter-clockwise, otherwise, they are cycling clockwise.
• ~s_i~ (~1 \le s_i \le 6~) is the amount of seconds taken for the cyclist to make a full revolution.

Output

Output ~N~ lines, the ~i~th of which has the smallest area of the polygon that can be projected after the ~i~th cyclist has joined.

Answers with a relative or absolute error of ~10^{-6}~ will be accepted.

Example 1

Input

5
1 0 0 3
1 1 0 4
0 2 1 6
-1 1 1 3
1 2 0 5

Output

0
0
1.18301270189253
3.36602540378446
3.34807621135265

Explanation

For the first 2 seconds, the convex polygon can have 0 area since the active cyclists can be contained on a point and line segment.

Example 2

Input

7
1 0 0 3
1 0 0 3
1 0 0 3
1 2 0 3
-10000 1000000 0 3
1000 0 0 3
2 3 0 3

Output

0
0
1.29903810567666
2.79903810567678
1616696.64279091
254830560.031683
254830560.031683

Explanation

In this input, all the cyclists are rotating about the origin in the same direction and angular speed, so it is almost as if they remained stationary.

Example 3

Input

8
10 12 1 5
0 5 1 6
9 9 0 1
10 10 0 1
-8 -3 1 2
5 -20 1 4
9 -30 0 6
1 20 0 6

Output

0
0
24.7874528984276
117.939288182412
218.065225495698
198.032032302769
690.458143401055
659.01583729355