Sequence Maintenance with Modulo Insertion and Query

You are given an initially empty sequence. You need to perform a series of operations on the sequence. There are two types of operations:

1. Query Operation

Syntax: Q L

Function: Query the maximum value among the last \(L\) numbers of the sequence and output that maximum value.

Constraint: \(L\) is a positive integer and does not exceed the current length of the sequence.

2. Insert Operation

Syntax: A n

Function: Let \(t\) be the answer of the most recent query (if no query has been performed yet, then \(t=0\)). Compute \((n + t) \mod D\) and append the result to the end of the sequence.

Constraint: \(n\) is an integer (which may be negative) and \(D\) is a given constant.

Input Format

The first line contains two integers \(N\) and \(D\), where \(N\) is the total number of operations, and \(D\) is the modulo constant.

The following \(N\) lines each contain an operation in one of the following formats: Q L for a query, or A n for an insertion.

Output Format

For each query operation, output the result (the maximum among the queried segment) on a separate line.

inputFormat

The first line contains two integers N and D (N is the number of operations and D is the modulo constant). The next N lines each contain an operation in one of the following formats:

• Q L: Query the maximum value among the last \(L\) numbers of the sequence. (\(1 \leq L \leq current sequence length\))
• A n: Insert operation. Compute \((n + t) \mod D\) and append the result, where \(t\) is the answer from the most recent query (or 0 if no query has been made).

outputFormat

For each query operation in the input, print the resulting maximum value on a separate line in the order they appear.

sample

6 100
A 10
A 20
A 5
Q 2
A -15
Q 3

20
20

</p>