LRU Cache Implementation

You are required to implement a Least Recently Used (LRU) Cache. The LRU Cache should support two operations: set(key, value) and get(key).

Operations:

• set key value: Insert or update the value for the given key. If the cache exceeds its capacity, remove the least recently used item.
• get key: Retrieve the value associated with the key. If the key does not exist, return -1.

Note: When a key is accessed either by get or updated by set, it becomes the most recently used entry.

The cache must be implemented such that both operations are efficient. The capacity and a sequence of operations will be provided from the standard input.

For an LRU Cache with a capacity \( C \), if a new element is added and the total number of elements exceeds \( C \), then the least recently used element will be evicted from the cache.

inputFormat

The first line of input contains two space-separated integers: capacity (the maximum number of entries the cache can hold) and Q (the number of operations).

The next Q lines each contain an operation. Each operation is either in the format:

• set key value — add or update an entry with the given key and value.
• get key — retrieve the value of the given key.

All inputs are read from standard input (stdin).

outputFormat

For each get operation, output the return value on a new line to standard output (stdout). There is no output for set operations.

## sample

2 5
set 1 1
set 2 2
get 1
set 3 3
get 2

1
-1

</p>