Akvarij

Ο 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~ από την επίσημη λύση.

Παραδείγματα

input

3 2
20 20 20
Q 20
Q 30

output

0.000
20.000

input

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

output

2.000
1.000
2.500

input

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

0.750
3.750
9.000
1.500
6.000
12.000

Επεξήγηση του 1ου παραδείγματος:

Η παρακάτω αριστερή εικόνα δείχνει την κατάσταση πριν και η δεξιά μετά το ερώτημα τύπου ~U~, για τη στάθμη νερού ~h = 2~ (ερώτημα ~Q\;2~). Στην πρώτη εικόνα, η βυθισμένη περιοχή ισούται με ~3.75~ και στη δεύτερη εικόνα είναι ~6~.