Let us use right trapezoids to build a wall. Each trapezoid is defined by four real parameters ℓ, r, y_{ℓ} and y_{r}, which indicate the points (ℓ, 0), (ℓ, y_{ℓ}), (r, y_{r}), and (r, 0). For instance, adding the trapezoids (1 5 1 3) and (7 11 1 3) into an empty wall produces the figure to the left:
(13,8) linestyle=dashed linecolor=green -(0,1)(13,1) -(1,0)(1,7) (2,0)1 (3,0)2 (4,0)3 (5,0)4 (6,0)5 (7,0)6 (8,0)7 (9,0)8 (10,0)9 (11,0)10 (12,0)11 (0,2)1 (0,3)2 (0,4)3 (0,5)4 (0,6)5 linestyle=solid linecolor=black -(2,1)(2,2) -(2,2)(6,4) -(6,4)(6,1) -(8,1)(8,2) -(8,2)(12,4) -(12,4)(12,1) (13,8) linestyle=dashed linecolor=green -(0,1)(13,1) -(1,0)(1,7) (2,0)1 (3,0)2 (4,0)3 (5,0)4 (6,0)5 (7,0)6 (8,0)7 (9,0)8 (10,0)9 (11,0)10 (12,0)11 (0,2)1 (0,3)2 (0,4)3 (0,5)4 (0,6)5 linestyle=solid linecolor=black -(2,1)(2,2) -(2,2)(4,3) -(4,3)(4,6) -(4,6)(6,6) -(6,6)(6,3) -(6,3)(8,2) -(8,2)(8,3) -(8,3)(10,3) -(10,3)(12,4) -(12,4)(12,1)
The material of the trapezoids is semifluid, so they adapt to the shape underneath. For instance, adding (3 9 3 0) to the figure to the left produces the figure to the right. Write a program to keep track of the shape of an initially empty wall, with two kind of operations:
Input
Input consists of several cases, each one with the number of operations n, followed by those operations. Assume 1 ≤ n ≤ 10^{5}, that all given parametres are real numbers between 0 and 10^{4}, ℓ < r, and that every x is different to all previous ℓ and r.
Output
For every ‘C’ operation, print the height at x with three digits after the decimal point. The input cases do not have precision issues.
Input
8 A 1 5 1 3 C 3 A 7 11 1 3 C 10 A 3 9 3 0 C 4 C 6.5 C 1000 3 A 0 10000 0 10000 A 1.2 3.4 100.7 23.42 C 2.789 1 C 10
Output
2.000 2.500 5.000 1.250 0.000 47.672 0.000