Loli là một lập trình viên có tiếng. Cô ấy đã cho ra đời một trình soạn thảo cực xịn xò. Tuy nhiên kỳ lạ là trình soạn thảo này chỉ làm việc với các số nguyên??

Ta có một con trỏ lệnh. Ban đầu trình soạn thảo không có số nào, dãy số hiện tại là rỗng. Loli thực hiện lần lượt ~q~ thao tác thuộc các dạng sau:

• ~I\ x~: Chèn số ~x~ ~(|x| \le 1000)~ vào ngay trước con trỏ lệnh.
• ~D~: Xoá số ngay trước con trỏ lệnh (hoặc không làm gì nếu con trỏ đã ở đầu dãy).
• ~L~: Di chuyển con trỏ lệnh sang trái một đơn vị (hoặc không làm gì nếu con trỏ đã ở đầu dãy).
• ~R~: Di chuyển con trỏ lệnh sang phải một đơn vị (hoặc không làm gì nếu con trỏ đã ở cuối dãy).

Bên trên đều là những lệnh bình thường của một trình soạn thảo. Tuy nhiên tính năng đặc biệt của trình soạn thảo nằm ở thao tác đặc biệt có dạng:

• ~Q\ k~: Giả sử dãy đứng trước con trỏ đánh số từ ~1~ tới ~n~ tính từ bên trái là ~a_1,a_2,...,a_n~, ta cần tính và in ra ~X = max(S_1, S_2, \dots, S_k)~, với ~S_i = a_1 + a_2 + ... + a_i~.

Yêu cầu:

• Thực hiện lần lượt ~q~ thao tác cho trước; với thao tác loại ~Q\ k~, cần tính và in ra ~X~.
• Sau khi thực hiện ~q~ thao tác, in ra dãy số cuối cùng của trình soạn thảo.

!! Chú ý nhập xuất từ file !!

Input

Nhập vào từ file "EDITOR.INP":

• Dòng đầu chứa số nguyên dương ~q~ ~(1\le q\le 5 \times 10^5)~ là số lượng thao tác.
• ~q~ dòng tiếp theo, mỗi dòng chứa một thao tác, theo dạng đã nói ở trên.
• Dữ liệu đảm bảo với các thao tác dạng ~Q\ k~ thì đã có ít nhất một số đứng trước con trỏ lệnh và ~k~ không quá số lượng số đứng trước con trỏ lệnh.

Output

In ra file "EDITOR.OUT":

• Với mỗi truy vấn dạng ~Q\ k~, in ra kết quả trên một dòng.
• Dòng cuối cùng in ra dãy số của trình soạn thảo sau khi thực hiện xong ~q~ thao tác.

Subtasks

• Subtask 1: ~50\%~ test có ~q\le 10^3~ và không có thao tác loại ~Q\ k~;
• Subtask 2: ~20\%~ test có ~q\le 10^3~;
• Subtask 3: ~30\%~ test còn lại không có ràng buộc gì thêm.

Sample Input 1

9
I 2
I -1
I 4
Q 3
L
D
I 5
R
Q 1

Sample Output 1

5
2
2 5 4

Giải thích:

Ban đầu ta có dãy số rỗng ~[]~, con trỏ ta tạm đánh dấu là ~|~ (chú ý tới ký hiệu con trỏ):

• Ba thao tác đầu là thao tác ~I~, sau khi thực hiện ta có ~[2\ -1\ 4|]~
• Thực hiện thao tác ~Q\ 3~, ta có ~S_1 = 2, S_2 = 1, S_3=5~. Vậy giá trị lớn nhất là ~X=5~.
• Thực hiện thao tác ~L~, ta có ~[2\ -1|\ 4]~.
• Thực hiện thao tác ~D~, ta xóa ~-1~, còn lại ~[2|\ 4]~.
• Thực hiện thao tác ~I\ 5~, ta có ~[2\ 5|\ 4]~.
• Thực hiện thao tác ~R~, ta có ~[2\ 5\ 4|]~
• Thực hiện thao tác ~Q\ 1~, ta có ~S_1 = 2~. Vậy giá trị lớn nhất là ~X=2~.
• Cuối cùng, in ra dãy số hiện tại, đó là ~[2\ 5\ 4]~.