LRU Cache Simulation

You are given a simulation of an LRU (Least Recently Used) Cache. The cache has a fixed capacity \(C\). You should process a sequence of queries, where each query is either:

• SET x y: Set the value y for the key x in the cache. If the key already exists, update its value and mark it as most recently used. If the cache is full and you have to insert a new key, remove the least recently used key.
• GET x: Retrieve the value for the key x. If the key exists, return its value (and mark it as most recently used); otherwise, return \(-1\).

Queries are processed in order. For every GET query, output the corresponding result on a new line.

Note: The ordering of the cache is updated for both queries: when a key is set (or reset) and when a key is retrieved.

inputFormat

The first line of input contains two space-separated integers:

1. \(C\): the capacity of the cache.
2. \(Q\): the number of queries.

This is followed by \(Q\) lines, each of which is either in the format SET x y or GET x, where x and y are integers.

outputFormat

For each GET query, output the result on a new line. If the key does not exist in the cache, output -1.

## sample

2 6
SET 1 10
SET 2 20
GET 1
SET 3 30
GET 2
GET 3

10
-1
30

</p>