Description

Original source: JSOI 2008

Given a sequence of positive integers $a_1, a_2, a_3, \cdots , a_n$, where each number is between $0\sim p – 1$. You can perform two types of operations on this sequence:

• Add operation: Append a number to the end of the sequence, increasing its length to $n + 1$;
• Query operation: Query the maximum number among the last $L$ numbers in the sequence.

At the start of the program, the integer sequence is empty. Write a program that reads the sequence of operations and outputs the answers to the query operations.

Input Format

The first line contains two positive integers $m, p$, as described in the problem statement;

The next $m$ lines each represent an operation. If the line is Q L, it means the operation is to query the maximum number among the last $L$ numbers in the sequence; if the line is A t, it means to append a number to the end of the sequence, where the appended number is $(t + a) \bmod p$. Here, $t$ is the input parameter, and $a$ is the answer to the last query operation before this append operation (if there were no prior query operations, then $a = 0$).

The first operation is guaranteed to be an add operation. For query operations, $L > 0$ and does not exceed the current length of the sequence.

Output Format

For each query operation, output one line containing a single number, which is the maximum number among the last $L$ numbers in the sequence.

Sample 1

The final sequence is $97, 14, 60, 96$.

10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99

97
97
97
60
60
97

Data Range and Hint

For all data, $1\le m\le 2\times 10^5, 1\le p\le 2\times 10^9, 0\le t\lt p$.