화면 보호기

상근이는 새 화면 보호기를 설치했다. 컴퓨터를 5분동안 사용하지 않으면 화면 보호기가 실행된다. 이 화면 보호기는 수족관 그림과 움직이는 물고기를 보여준다. 화면 보호기 설정 화면에서는 바닥의 모양과 수면의 높이를 설정할 수 있다.

수족관은 너비가 N-1인 2차원 평면으로 나타낼 수 있다. 이때, N은 양의 정수이다. 수족관의 가장 왼쪽 x좌표는 0이고, 가장 오른쪽 x좌표는 N-1이다. 각 정수 x좌표 i는 바닥의 높이 Hi를 갖는다. 이 높이는 설정에서 바꿀 수 있다. 바닥은 인접한 두 x좌표 i와 i+1를 이용해서 (i, Hi)와 (i+1, Hi+1)을 연결하는 선분으로 나타낼 수 있다.

수면의 높이가 h라면, 수족관의 바닥과 y=h 사이의 모든 공간이 물로 채워지게 된다. 만약, h보다 높은 바닥이 있다면, 그 곳은 섬이다.

상근이는 설정에서 수족관 바닥 좌표와 수면의 높이를 바꿀 때 마다 물로 채워지는 곳의 넓이를 구하려고 한다.

첫째 줄에 두 양의 정수 N과 상근이가 설정을 바꾼 횟수 M이 주어진다. (3 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000)

둘째 줄에는 N개의 정수 바닥의 초기 높이 Hi가 공백으로 구분되어 주어진다. (0 ≤ Hi ≤ 1000)

다음 M개 줄에는 상근이가 설정에서 무엇을 바꾸었는 지가 주어진다.

Q h는 수면의 높이를 h로 바꾸었다는 뜻이다. (0 ≤ h ≤ 1000)

U i h는 x좌표가 i인 곳의 바닥의 높이를 h로 바꾸었다는 뜻이다. (0 ≤ i ≤ N-1, 0 ≤ h ≤ 1000) 즉, Hi = h

Q로 시작하는 변경이 주어질 때 마다, 물로 채워지는 곳의 넓이를 소수점 셋째 자리까지 출력한다.