LRU Cache Implementation

Implement a Least Recently Used (LRU) Cache that supports the following operations:

• get key: Return the value associated with key if it exists in the cache; otherwise, return -1.
• set key value: Insert the key with its value into the cache. If the cache is full, invalidate the least recently used item before inserting the new one. If the key already exists, update its value and mark it as most recently used.

You will receive a sequence of operations as input via stdin. For each get operation, print the result on a new line to stdout.

The cache operations must be implemented efficiently. Internally, you may use the following approach: when a key is accessed or updated, it becomes the most recently used; when capacity is reached, the key that has not been used for the longest time gets evicted.

In the context of this problem, consider the LRU policy as follows. For two keys k1 and k2, if k1 was accessed more recently than k2, then k2 is considered least recently used.

All formulas, if any, should be written in LaTeX format (for instance, the eviction condition can be stated as: \(\text{if } |\text{cache}| \geq \text{capacity} \text{ then evict the key with minimal recent access time.}\))

inputFormat

The first line of input contains two integers: capacity (the maximum number of elements the cache can hold) and n (the total number of operations). Each of the next n lines contains an operation in one of the following formats:

• set key value • get key

For example:

2 9 set 1 1 set 2 2 get 1 set 3 3 get 2 set 4 4 get 1 get 3 get 4

outputFormat

For each get operation, output the corresponding value on a separate line. If the key is not found, output -1.## sample

2 9
set 1 1
set 2 2
get 1
set 3 3
get 2
set 4 4
get 1
get 3
get 4

1
-1
-1
3
4