LRU Cache Implementation

Implement an LRU (Least Recently Used) Cache that supports two operations: set and get.

The set operation inserts a key with a given value or updates the value if the key already exists. If the cache is at full capacity, then the least recently used item should be evicted before inserting a new item.

The get operation retrieves the value associated with a given key. If the key exists, it returns the value and marks the key as recently used; otherwise, it returns -1.

Note: Both operations are expected to have a time complexity of $O(1)$. For example, consider an LRU cache with capacity 2:

set 1 1      // Cache: {1=1}
get 1        // Returns 1
set 2 2      // Cache: {1=1, 2=2}
get 1        // Returns 1, now 1 is MRU
set 3 3      // Evicts key 2, Cache: {1=1, 3=3}
get 2        // Returns -1
get 3        // Returns 3

inputFormat

The first line contains two integers separated by a space: capacity (the maximum capacity of the cache) and n (the number of operations).

Each of the following n lines contains an operation in one of the following formats:

• set key value — Insert or update the key with the provided value.
• get key — Retrieve the value associated with the key. If not found, output -1.

outputFormat

For each get operation, output the returned value on a separate line to stdout.## sample

2 7
set 1 1
get 1
set 2 2
get 1
set 3 3
get 2
get 3

1
1
-1
3