Hàng đợi hai đầu

3M là một học sinh chuyên Văn nhưng cô ấy rất ham mê tìm hiểu các cấu trúc dữ liệu.
Hôm nay cô ấy được thầy Nhật dạy về cấu trúc dữ liệu deque, thứ có thể giúp bạn
thêm bớt ở cả hai đầu của một dãy số. Sau khi học xong, 3M đã nghĩ ra một bài toán
truy vấn rất hấp dẫn và tự đặt ra cho mình câu hỏi: "Liệu bài này có thể làm bằng deque
hay không?".

Bài toán được mô tả như sau: Cho dãy số gồm \(n\) phần tử và có \(q\) truy vấn thuộc một
trong hai dạng sau:

• POFPUB x: Lấy phần tử đầu tiên của dãy và thêm nó vào cuối dãy. Lặp lại
  thao tác đó \(x\) lần (\(1 \le x \le 10^{9}\)).
• SUM l r: Tính tổng các phần tử nằm trên đoạn \([l, r]\) (\(1 \le l \le r \le n\)).

Input

Nhập từ file DEQUE.INP:

• Dòng đầu tiên chứa hai số nguyên dương \(n, q\) (\(1 \le n \le 10^{6},\ 1 \le q \le 10^{6}\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^{9}\)).
• \(q\) dòng tiếp theo, mỗi dòng là một truy vấn thuộc một trong hai dạng đã nêu.

Output

Ghi ra file DEQUE.OUT:

• Với mỗi truy vấn SUM l r, in ra tổng các phần tử trong đoạn \([l, r]\).

Example

5 5
2 3 2 4 5
POFPUB 2
SUM 3 5
POFPUB 2
SUM 3 5
SUM 1 5

10
9
16

3 3
1 1 1
POFPUB 17
SUM 1 2
SUM 1 3

2
3

Scoring

• \(30\%\) số test tương ứng với \(30\%\) số điểm: \(1 \le n, q \le 1000\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm: \(a_1 = a_2 = \cdots = a_n\).
• \(10\%\) số test tương ứng với \(10\%\) số điểm: với mọi truy vấn SUM, ta có \(l = 1, r = n\).
• \(40\%\) số test tương ứng với \(40\%\) số điểm còn lại: không có ràng buộc gì thêm.