Description

Xiao Z is an elementary school student who loves math. Recently, he has been studying properties of integer sequences.

To facilitate his research, Xiao Z wants to implement a sequence editor called "Open Continuous Lines Processor".

At the beginning, the sequence editor contains no numbers, only a cursor. This sequence editor needs to support five operations.

• I x Insert the number $x$ immediately before the cursor.
• D Delete the number immediately before the cursor.
• L Move the cursor one position to the left.
• R Move the cursor one position to the right.
• Q k Let the sequence before the cursor be $\{a_1, a_2, \cdots, a_n\}$. Output the maximum prefix sum among the first $k$ positions, i.e., $\max_{1 \le i \le k} \sum_{j=1}^{i} a_j$. It is guaranteed that $k \leqslant n$.

Input Format

The first line contains an integer $N$, indicating the number of operations.

Then follow $N$ lines, each containing one command.

Output Format

For each Q k command, output an integer representing the answer to that operation.

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

2
3

Hint

Constraints

For $50\%$ of the testdata, $N \leqslant 1000$.

For $80\%$ of the testdata, $N \leqslant 10^5$.

For $100\%$ of the testdata, $N \leqslant 10^6$, and the absolute value of each inserted number does not exceed $1000$.

It is guaranteed that the D operation will not be performed when the sequence editor is empty.

Translated by ChatGPT 5