Cho một trình quản lý số với một con trỏ lệnh. Ban đầu dãy số được quản lý là rỗng. Có \(q\) thao tác thuộc các dạng sau:

• \(I\) \(x\): Chèn số \(x\) \((|x| \leq 1000)\) vào ngay trước con trỏ lệnh

• \(D\) \(x\): Xóa 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)

• \(Q\) \(k\): Giả sử dãy đứng trước con trỏ là \(a_1, a_2, \ldots, a_n\), cần tính \(max_{i=1}^k (a_1+a_2+\ldots+a_i)\)

Input

• Dòng đầu chứa số nguyên dương \(q\) \((1 \leq q \leq 10^6)\)

• Mỗi dòng trong \(q\) dòng tiếp theo chứa một truy vấ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

• Với mỗi truy vấn dạng \(Q\) \(k\), in ra kết quả trên một dòng.

Example

8
I 2
I -1
I 1
Q 3
L
D
R
Q 2 

2
3