Bounded History Max Tracker

You maintain a bounded history of the most recent k integers added. This is NOT a fixed sliding step over a whole array; it simply grows one ADD at a time and a QUERY asks about whatever is currently held.

Process n operations, in order:

• ADD x - record integer x as the newest value. If the history already holds k values, the oldest one is discarded first.
• QUERY - print the maximum value currently stored in the history. If the history is empty, print NONE instead.

Print one line of output per QUERY operation, in the order they occur.

Input format

Line 1: two integers n and k. Lines 2..n+1: one operation per line, either ADD x or QUERY.

Output format

One line per QUERY operation: either the current maximum, or NONE.

Constraints

• 1 <= n <= 100000
• 1 <= k <= 100000
• -1000000 <= x <= 1000000
• It is guaranteed that at least one QUERY operation appears in the input.