LRU Cache Implementation

In this problem, you are required to implement a Least Recently Used (LRU) cache. The cache should be able to perform the following two operations:

• get(key): Returns the value associated with the key if it exists in the cache, otherwise returns \( -1 \).
• put(key, value): Inserts or updates the key with the given value. If the cache is already at full capacity, it should evict the least recently used key before inserting the new key-value pair.

The least recently used item is the one that has not been accessed or updated for the longest time. You are expected to maintain this order during both get and put operations.

Note: All operations should run in optimal time complexity. Use appropriate data structures to achieve the required performance.

Example:

Input:
1 5
put 1 1
get 1
put 2 2
get 1
get 2
Output:
1
-1
2

</p>

Here, the first number in the input specifies the capacity of the cache and the second number specifies the number of operations to follow. Each subsequent line specifies an operation in one of the following formats:

• put key value
• get key

inputFormat

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

The following n lines each contain an operation. An operation is one of the two forms:

• put key value
• get key

For each get operation, output the result on a new line.

outputFormat

For every get operation, print the corresponding value returned by the LRU cache on a new line. If the key is not present in the cache, print \( -1 \).

## sample

1 5
put 1 1
get 1
put 2 2
get 1
get 2

1
-1
2

</p>