Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT133B - Bể cá

Một bể cá 2D có gồm N-1 cột, và lề của mỗi cột được đánh dấu tọa độ. Lề trái của cột đầu tiên có hoành độ là 0, lề phải của cột ngoài cùng bên phải có hoành độ là N.

Trong lòng bể cá được xây dựng các hòn đảo. Với mỗi i (0 ≤ i ≤ N), H_i là độ cao của vùng đảo so với mặt nền.

Khi mực nước dâng lên tới độ cao h, các vùng đất thấp hơn mặt nước sẽ bị ngập. Nhiệm vụ của bạn là tính xem có bể cá đang chứa bao nhiêu đơn vị nước?

Input

Dòng đầu tiên gồm 2 số N và M. (3 ≤ N ≤ 100 000, 1 ≤ M ≤ 100 000), trong đó M là số yêu cầu cần thực hiện.

Dòng thứ 2 gồm N số H_i là độ cao của vùng đất tại tại hoành độ i. (0 ≤ H_i ≤ 1000).

M dòng sau, mỗi dòng là 1 query, có 2 dạng như sau:

*) Q h: Độ cao của mực nước trong bể cá là h và yêu cầu tính toán số lượng nước đang có trong bể cá (0 ≤ h ≤ 1000).

*) U i h: Thay đổi độ cao của vùng đất tại hoành độ i thành H_i = h (0 ≤ h ≤ 1000).

Output

Với mỗi query dạng 1, hãy in ra đáp số của bài toán, làm tròn đến 3 chữ số sau dấu phảy (sai số không quá 10-3).

Example

Input:
Test 1:

3 2

20 20 20

Q 20

Q 30

Test 2:

3 5

0 2 0

Q 2

U 1 1

Q 1

U 1 10

Q 5

Test 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

 

Output:
Test 1: 

0.000

20.000

Test 2:

2.000

1.000

2.500

Test 3:

0.750

3.750

9.000

1.500

6.000

12.000

 

Hình minh họa cho test 3, trường hợp h = 2 trước và sau khi update.

 

Được gửi lên bởi:adm
Ngày:2013-02-08
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.