# Building a wall P27780

Statement

thehtml

Let us use right trapezoids to build a wall. Each trapezoid is defined by four real parameters ℓ, r, y and yr, which indicate the points (ℓ, 0), (ℓ, y), (r, yr), 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:

unit=0.45cm

(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:

• A’ ℓ ⁠ ⁠ r ⁠ ⁠ y⁠ ⁠ yr, to add a trapezoid as already explained.
• Cx, to consult the current height of the wall at the abscissa x.

Input

Input consists of several cases, each one with the number of operations n, followed by those operations. Assume 1 ≤ n ≤ 105, that all given parametres are real numbers between 0 and ‍104, ℓ < 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.

Public test cases
• 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
```
• Information
Author