Dù đã tìm đủ mọi cách tự sát nhưng mà không thể nào tự sát được vì quá ngoan,Conan thất vọng tràn trề,quay trở lại với VOJ,nhìn những bài đã Accepted,Conan bỗng nảy ra một ý,tại sao không kết hợp những bài đó với nhau nhỉ,và cuối cùng anh đã quyết định kết hợp hai bài QMAX2 và GSS lại với nhau trở thành problem CONANGSS như sau :

Cho một dãy số n phần tử ( tất cả khởi tạo bằng 0 ),và m câu hỏi (n<=20.000,m<=20.000). Mỗi câu hỏi có dạng:

U u v val tức là tăng cả đoạn (u,v) lên val đơn vị ( val có thể âm )

Q u v ,khi gặp câu hỏi này bạn phải trả lời ra đoạn con có tổng lớn nhất trong đoạn (u,v) (Định nghĩa đoạn con giống bài GSS).

Input

-Dòng đầu ghi 2 số n,m

-m dòng sau mỗi dòng ghi 1 trong 2 loại câu hỏi như trên

Output

Với mỗi câu hỏi dạng Q in ra kết quả

Example

Input:
4 2
U 1 3 2
Q 1 4
Output:
6
Chú ý:
Nghiêm cấm for trâu dưới mọi hình thức :))/
/