Clipboard History Manager

You are given a series of operations on a clipboard history. The clipboard stores text snippets. There are two types of operations:

• INSERT <text> — Insert the given text snippet at the beginning of the clipboard history.
• RETRIEVE <position> — Retrieve the text snippet at the specified position in the history. The most recently inserted item is at position 1, the next at position 2, and so on. If the requested position is invalid (i.e. less than 1 or greater than the number of inserted snippets), output None.

Your task is to simulate these operations. The input is provided via standard input (stdin) and the output must be printed to standard output (stdout). For every RETRIEVE operation, print the corresponding result on its own line.

The retrieval behavior can be expressed by the formula in LaTeX: $$result = \begin{cases} clipboard_{position} & \text{if } 1 \leq position \leq size(clipboard)\\ \text{None} & \text{otherwise} \end{cases}$$

inputFormat

The first line of input contains a single integer n which represents the number of operations.

The next n lines each contain an operation. Each operation is either an insertion in the format INSERT <text> or a retrieval in the format RETRIEVE <position>.

Note: The operations are processed in the order they appear in the input.

outputFormat

For every RETRIEVE operation, output the retrieved text snippet on its own line. If the position is invalid, output None (without quotes).

## sample

6
INSERT Hello
INSERT World
RETRIEVE 1
RETRIEVE 2
INSERT Foo
RETRIEVE 1

World
Hello
Foo

</p>