Mirko has recently installed a new screensaver. If he is away from the keyboard for five minutes, the screen shows a picture of an aquarium with animated fish. The screensaver has settings for customizing the shape of the (virtual, sandy) aquarium bottom, as well as the water level.

The aquarium can be represented in a 2D Cartesian coordinate system as a shape $N-1$ columns wide, where $N$ is a positive integer. The left wall of the aquarium has the x-coordinate of $0$, and the right wall has the x-coordinate of $N-1$. Each integer-valued x-coordinate of the aquarium bottom (let us denote it by $i$) from $0$ to $N-1$ has a separately adjustable height of $H_i$. Between any two adjacent integer-valued x-coordinates $i$ and $i+1$, the bottom can be described by a line segment between points $(i,H_i)$ and $(i+1,H_{i+1})$.

If the water level is set to $h$, the water fills the area between the line $y=h$ and the aquarium bottom. If a part of the aquarium bottom is above the water level $h$, it forms an island and is not submerged.

For different shapes of the aquarium bottom, Mirko would like to know the total area of his screen covered by water. Help Mirko find answers to his questions (other than $42$).

Input Specification

The first line of input contains two positive integers, $N$ ($3\le N\le 100000$, the length of the bottom) and $M$ ($1\le M\le 100000$, the number of queries).

The second line of input contains $N$ space-separated nonnegative integers $H_i$ $(0\le H_i\le 1000)$, the starting bottom heights.

Each of the following $M$ lines contains a single query with one of the following two types:

• Q h – if the water level is set to $h$ $(0\le h\le 1000)$, assuming the current bottom shape, what is the total screen area covered by water?
• U i h – Mirko has decided to change the bottom height at x-coordinate $i$ $(0\le i\le N-1)$ to $h$ $(0\le h\le 1000)$; in other words, set $H_i=h$.

Output Specification

For each query with type $Q$, output a single line containing the required area, rounded to exactly three decimals. The area given is allowed to differ by at most $0.001$ from the official solution.

Sample Input 1

3 2
20 20 20
Q 20
Q 30

Sample Output 1

0.000
20.000

Sample Input 2

3 5
0 2 0
Q 2
U 1 1
Q 1
U 1 10
Q 5

Sample Output 2

2.000
1.000
2.500

Sample Input 3

7 7
0 2 1 3 2 1 0
Q 1
Q 2
Q 3
U 3 0
Q 1
Q 2
Q 3

Sample Output 3

0.750
3.750
9.000
1.500
6.000
12.000

Explanation for Sample Output 3

The left image below shows the situation before, and the right one after the U-type query, for water level $h=2$ (query Q 2). In the first image, the submerged area equals $3.75$, and in the second image it is $6$.