[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/taip2012-problems.pdf]

To go on holidays, Horacio and Hernan have sacrificed their participation in an important programming contest. While you are in this contest, they are close to the Andes driving along Highway 40, in Argentina, enjoying a pleasant view of the mountains in the horizon. Right now the sky over the highway is a clear, uniform blue, while the visible part of the mountains is a profile presenting rich and attractive textures. This worries Horacio and Hernan, because they fear that the pictures they are taking will be very expensive to print correctly. For this reason, in the next stop they will take out their laptops and write a program to estimate the area of the mountain profile that has to be printed in each picture. Can you finish this program before them?

Horacio and Hernan will be modeling the mountain profile in the following way. Each mountain is represented by an isosceles triangle whose base rests on the X axis of the XY plane. Two equal-length sides connect the endpoints of the base to the opposite vertex of the triangle, which is the tip of the corresponding mountain. To describe the position and shape of the triangle, we use the coordinates along the X axis of the base's endpoints, along with the height of the mountain.

The figure below is the model of a mountain profile formed by 4 mountains that are overlapping with one another. The area of the mountain profile that you have to calculate is marked with stripes. The lowest mountain of the figure is described by the values I = 4 (the left endpoint of the mountain base), D = 5 (the right endpoint of the mountain base)  and H = 1 (the height of the mountain).

In this problem, you are given the representation of the mountain profile, and you have to find the area of the union of all the corresponding triangles, in such a way that the overlapping parts are counted only once.

Input

Each test case is described using several lines. The first line contains a single integer number N, indicating the number of mountains (1 ≤ N ≤ 1000). Each of the N following lines describes a mountain using three integer numbers I, D and H, representing respectively the X coordinate of the left endpoint of the base, the same for the right endpoint of the base, and the height of the mountain (1 ≤ I, D, H ≤ 10⁵ with I < D). In each test case there are no two mountains that are exactly the same (that is, with equal values for the three parameters I, D and H). The end of the input is signalled by a line containing the number -1.

Output

For each test case, you should print a single line containing a rational number, representing the area of the corresponding mountain profile. Round the result to the closest rational with two decimal digits. In case of ties, round up. Note that you should always use exactly two digits after the decimal dot, even if this means ending with a zero.

Example

Input:
4
4 5 1
2 4 2
3 5 3
3 7 2
1
1 2 1
2
10 20 20
20 40 10
2
15 25 20
20 40 10
7
99998 99999 25000
99998 100000 50000
99996 100000 100000
1 3 100000
2 5 100000
1 5 60000
1 99999 100000
5
2 3 10
4 5 6
6 8 11
12 14 3
1 13 2
-1
Output:
6.90
0.50
200.00
190.00
5000331093.88
28.91