Mirko gần đây đã cài đặt một trình bảo vệ màn hình mới. Nếu anh ta rời khỏi bàn phím trong năm phút, màn hình sẽ hiển thị hình ảnh một bể cá với những chú cá hoạt hình. Trình bảo vệ màn hình có các cài đặt để tùy chỉnh hình dạng của đáy bể cá (ảo, cát), cũng như mực nước.

Bể cá có thể được biểu diễn trong hệ tọa độ Descartes 2D dưới dạng hình ~N – 1~ cột, trong đó ~N~ là số nguyên dương. Vách bên trái của bể cá có tọa độ ~x~ là ~0~, vách bên phải có tọa độ ~x~ là ~N – 1~. Mỗi tọa độ x có giá trị nguyên của đáy bể cá (gọi là ~i~) từ ~0~ đến ~N – 1~ có độ cao điều chỉnh riêng ~H_i~. Giữa hai tọa độ ~x~ nguyên ~i~ và ~i + 1~ liền kề bất kỳ, đáy có thể được mô tả bằng một đoạn thẳng nối các điểm ~(i, H_i)~ và ~(i + 1, H_i + 1)~.

Nếu mực nước được đặt thành h thì nước sẽ lấp đầy khu vực giữa đường ~y = h~ và đáy bể cá. Nếu một phần đáy bể cao hơn mực nước h thì tạo thành hòn đảo và không bị ngập nước.

Đối với các hình dạng khác nhau của đáy bể cá, Mirko muốn biết tổng diện tích màn hình được bao phủ bởi nước. Giúp Mirko tìm câu trả lời cho câu hỏi của anh ấy (ngoài 42 câu hỏi).

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ ~(3 \le N \le 100 000~, độ dài đáy~)~ và ~M~ ~(1 \le M \le 100 000~, số lượng truy vấn~)~.
• Dòng thứ 2 chứa ~N~ số nguyên không âm cách nhau bằng dấu cách ~H_i~ ~(0 ≤ Hi ≤ 1000)~, độ cao bắt đầu từ đáy.
• Mỗi ~M~ dòng sau chứa một câu truy vấn thuộc một trong hai loại sau:
• ~Q~ ~h~ – nếu đặt mực nước là ~h~ ~(0 ≤ h ≤ 1000)~, giả sử hình dạng đáy hiện tại thì tổng diện tích màn chắn bị nước bao phủ là bao nhiêu?
• ~U~ ~i~ ~h~ – Mirko đã quyết định thay đổi độ cao đáy tại tọa độ ~x~ ~i~ ~(0 \le i \le N - 1)~ thành ~h~ ~(0 \le h \le 1000)~ nói cách khác, đặt ~H_i = h~

Output

• Đối với mỗi truy vấn có loại ~Q~, xuất ra một dòng chứa diện tích được yêu cầu, được làm tròn đến chính xác ba số thập phân. Diện tích đã cho được phép sai khác tối đa ~0,001~ so với nghiệm chính thức.

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

Làm rõ ví dụ thứ ba:

• Hình bên trái bên dưới thể hiện tình huống trước và bên phải sau truy vấn kiểu chữ ~U~, đối với mực nước ~h = 2~ (truy vấn ~Q~ ~2~). Trong hình ảnh đầu tiên, diện tích ngập nước bằng ~3,75~ và trong hình ảnh thứ hai là ~6~.