Open Continuous Lines Processor

Little Z is a math-loving elementary school student. Recently, he has been studying some properties of integer sequences. To help his research, he wants to implement a sequence editor called "Open Continuous Lines Processor." Initially, the editor is empty except for a cursor. The editor supports the following five operations:

• I x: Insert the integer x immediately before the current cursor. After insertion, the cursor is positioned immediately after the inserted number.
• D: Delete the number immediately before the cursor. It is guaranteed that there is a number to delete when this command is executed.
• L: Move the cursor one position to the left. It is guaranteed that the cursor is not at the beginning.
• R: Move the cursor one position to the right. It is guaranteed that the cursor is not at the end.
• Q k: Let the sequence before the cursor be \(\{a_1,a_2,\cdots,a_n\}\). For the given integer k (with \(1 \le k \le n\)), output the maximum prefix sum among the first k numbers. In mathematical notation, output \[ \max_{1 \le i \le k} \left(\sum_{j=1}^{i} a_j\right). \]

Process the operations in the given order. For every Q (query) operation, output its result on a new line.

inputFormat

The input begins with a single integer Q (\(1 \le Q \le 10^5\)) representing the number of operations. The next Q lines each contain one of the following commands:

• I x: Insert operation with an integer x (\(|x|\) may be large).
• D: Delete operation.
• L: Move cursor left.
• R: Move cursor right.
• Q k: Query operation where k is an integer satisfying \(1 \le k \le n\), and \(n\) is the current number of elements before the cursor.

outputFormat

For each query operation (Q k), output a single integer representing the maximum prefix sum of the first k numbers in the current sequence (i.e. the maximum value of \(a_1,\; a_1+a_2,\; \ldots,\; \sum_{j=1}^{k}a_j\)). Each output should be printed on its own line.

sample

5
I 3
I -2
Q 2
L
Q 1

3
3