Mirko 最近安装了一个新的屏幕保护程序。如果他离开键盘五分钟，屏幕上就会显示一个带有动画鱼的水族箱画面。该屏幕保护程序具有自定义（虚拟的、沙质的）水族箱底部形状以及水位的设置。

水族箱可以在二维笛卡尔坐标系中表示为一个宽为 $N - 1$ 列的形状，其中 $N$ 是一个正整数。水族箱的左侧墙壁的 x 坐标为 $0$，右侧墙壁的 x 坐标为 $N - 1$。水族箱底部的每个整数 x 坐标（我们用 $i$ 表示）从 $0$ 到 $N - 1$ 都有一个可单独调节的高度 $H_i$。在任意两个相邻的整数 x 坐标 $i$ 和 $i + 1$ 之间，底部可以由连接点 $(i, H_i)$ 和 $(i + 1, H_{i + 1})$ 的线段来描述。

如果水位设置为 $h$，水将充满直线 $y = h$ 与水族箱底部之间的区域。如果水族箱底部的某一部分高于水位 $h$，它就会形成一个岛屿，不会被淹没。

对于不同的水族箱底部形状，Mirko 想要知道屏幕上被水覆盖的总面积。请帮助 Mirko 找到他问题的答案（除了 42 以外）。

输入格式

输入的第一行包含两个正整数 $N$（$3 \le N \le 100\,000$，底部的长度）和 $M$（$1 \le M \le 100\,000$，询问的数量）。

第二行包含 $N$ 个空格分隔的非负整数 $H_i$（$0 \le H_i \le 1000$），表示初始的底部高度。

接下来的 $M$ 行，每行包含一个以下两种类型之一的询问：

• Q h – 如果水位设置为 $h$（$0 \le h \le 1000$），在当前的底部形状下，被水覆盖的屏幕总面积是多少？
• U i h – Mirko 决定将 x 坐标为 $i$（$0 \le i \le N - 1$）处的底部高度修改为 $h$（$0 \le h \le 1000$）；换句话说，即设置 $H_i = h$。

输出格式

对于每个类型为 Q 的询问，输出一行，包含所需的面积，四舍五入保留恰好三位小数。允许输出的面积与官方答案的绝对误差不超过 $0.001$。

样例

输入样例 1

3 2 
20 20 20 
Q 20 
Q 30

输出样例 1

0.000 
20.000

输入样例 2

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

输出样例 2

2.000 
1.000 
2.500

输入样例 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

输出样例 3

0.750 
3.750 
9.000 
1.500 
6.000 
12.000

说明

第三个样例的解释：下图左侧显示了在进行 U 类型修改之前的状况，右侧显示了修改之后的状况，此时水位 $h = 2$（对应询问 Q 2）。在第一幅图中，被水淹没的面积等于 $3.75$，而在第二幅图中，该面积为 $6$。