Building a wall P27780

Statement

Let us use right trapezoids to build a wall. Each trapezoid is defined by four real parameters $\ell$ , $r$ , $y_\ell$ and $y_r$ , which indicate the points $(\ell, 0)$ , $(\ell, y_\ell)$ , $(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) (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 (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) (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 (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’ $\ell \enspace r \enspace y_\ell \enspace y_r$ , to add a trapezoid as already explained.
‘C’ $x$ , 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 \le n \le 10^5$ , that all given parametres are real numbers between 0 and $10^4$ , $\ell < r$ , and that every $x$ is different to all previous $\ell$ 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

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++ Rust