화면 보호기

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

수족관은 너비가 $N-1$인 2차원 평면으로 나타낸다. 가장 왼쪽 $x$좌표는 $0$, 가장 오른쪽 $x$좌표는 $N-1$이고, 각 정수 $x$좌표 $i$에는 바닥의 높이 $H_i$가 정해져 있다. 바닥은 인접한 두 좌표 $i$와 $i+1$에 대해 점 $(i, H_i)$와 $(i+1, H_{i+1})$을 잇는 선분으로 이루어진다.

수면의 높이가 $h$이면 바닥과 직선 $y = h$ 사이의 공간이 모두 물로 채워진다. 바닥이 $h$보다 높은 부분은 물에 잠기지 않는 섬이 된다.

상근이가 설정에서 바닥의 높이나 수면의 높이를 바꿀 때마다, 그 순간 물로 채워지는 영역의 넓이를 구하려고 한다.

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

둘째 줄에는 바닥의 초기 높이 $H_0, H_1, \dots, H_{N-1}$이 공백으로 구분되어 주어진다. ($0 \le H_i \le 1000$)

다음 $M$개의 줄에는 상근이가 바꾼 내용이 한 줄에 하나씩 주어지며, 형식은 다음 두 가지 중 하나이다.

• Q h : 수면의 높이를 $h$로 바꾼다. ($0 \le h \le 1000$)
• U i h : $x$좌표가 $i$인 곳의 바닥 높이를 $h$로 바꾼다. 즉 $H_i = h$가 된다. ($0 \le i \le N-1$, $0 \le h \le 1000$)

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