Implement LRU Cache

Implement a Least Recently Used (LRU) Cache.

You need to support two operations:

• put(key, value): Insert or update the key with the given value. If the cache is at capacity, the least recently used key should be removed.
• get(key): Retrieve the value associated with the key, or return -1 if the key does not exist in the cache. Accessing a key with get marks it as most recently used.

Your implementation should maintain the order of keys according to their recent usage. Aim to achieve efficient operations.

Note: Any formulas in the description would be rendered in \(\LaTeX\) format, though none are needed in this problem.

inputFormat

The input is given via stdin as follows:

1. The first line contains an integer capacity, the maximum capacity of the cache.
2. The second line contains an integer n, the number of operations.
3. The next n lines each contain an operation in one of two formats:

• put key value
• get key

outputFormat

For each get operation, output the result on a new line to stdout. The put operations do not produce output.

## sample

2
9
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

1
-1
-1
3
4

</p>