Description

You are asked to maintain a sequence and support the following two operations:

1. Query operation.

Syntax: Q L

Function: Query the maximum number among the last $L$ numbers in the current sequence, and output its value.

Constraint: $L$ does not exceed the current length of the sequence. $(L > 0)$

2. Insert operation.

Syntax: A n

Function: Add $t$ to $n$, where $t$ is the answer to the most recent query operation (if no query has been performed yet, then $t = 0$). Then take the result modulo a fixed constant $D$, and insert the obtained value at the end of the sequence.

Constraint: $n$ is an integer (possibly negative) and within the 64-bit signed integer range.

Note: Initially, the sequence is empty and contains no numbers.

Input Format

The first line contains two integers, $M$ and $D$, where $M$ is the number of operations and $D$ is the fixed constant mentioned above.

Each of the next $M$ lines contains one string describing a specific operation, with syntax as described above.

Output Format

For each query operation, output the result in order, one per line.

5 100
A 96
Q 1
A 97
Q 1
Q 2

96
93
96

Hint

Constraints

For all testdata, it is guaranteed that $1 \leq M \leq 2 \times 10^5$, $1 \leq D \leq 2 \times 10^9$.

Translated by ChatGPT 5