题目描述

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).

输入格式

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

The second line of input contains $N$ space-separated nonnegative integers $H_i$ ($0 \leq H_i \leq 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 \leq h \leq 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 \leq i \leq N - 1$) to $h$ ($0 \leq h \leq 1000$); in other words, set $H_i = h$.

输出格式

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.

3 2
20 20 20
Q 20
Q 30

0.000
20.000 

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

2.000
1.000
2.500

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

0.750
3.750
9.000
1.500
6.000
12.000 

提示

Clarification of the third example: 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$.