Circular Log Buffer Lookback

A monitoring system keeps a circular log buffer that stores AT MOST the most recent c events (the oldest is dropped once more than c events have been logged). Process n operations, in order:

• LOG x - record integer x as the newest event. If the buffer already holds c events, the oldest is dropped first.
• BACK j - print the value of the event that is j steps back from the newest event CURRENTLY in the buffer, where BACK 0 means the newest event itself, BACK 1 the one before it, and so on. If the buffer currently holds fewer than j + 1 events, print NONE instead.

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

Input format

Line 1: two integers n and c. Lines 2..n+1: one operation per line, either LOG x or BACK j.

Output format

One line per BACK operation: either the looked-up value, or NONE.

Constraints

• 1 <= n <= 100000
• 1 <= c <= 100000
• 0 <= j <= 100000
• -1000000 <= x <= 1000000
• It is guaranteed that at least one BACK operation appears in the input.