LRU Cache Implementation

Implement an LRU (Least Recently Used) Cache with O(1) time complexity for both the get and put operations. The cache holds a fixed number of key-value pairs. When the cache reaches its capacity, it evicts the least recently used item before inserting a new one.

Operations:

• get(key): Return the value associated with the key if it exists in the cache; otherwise, return -1.
• put(key, value): Insert the (key, value) pair into the cache. If the cache is full, evict the least recently used item before inserting the new pair.

Input/Output: The program will read from standard input (stdin) and write to standard output (stdout). The first line of input contains two integers: the capacity of the cache and the number of operations. Each subsequent line contains an operation in one of the following formats:

• put key value
• get key

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

Example:

Input:
2 9
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4
Output:
1
-1
-1
3
4

</p>

Note: Both the get and put operations must be performed in O(1) time complexity. In formal terms, if we denote the cache capacity by \(C\) and the number of operations by \(N\), your implementation must operate in \(O(N)\) total time, with each operation taking constant time.

inputFormat

The input is given via standard input (stdin) and has the following format:

The first line contains two space-separated integers:
- capacity: Maximum number of key-value pairs the cache can store.
- n: Number of operations to perform.

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

• put key value — Inserts the key-value pair into the cache.
• get key — Retrieves the value associated with the key. If the key does not exist, output -1.

outputFormat

For each get operation, output the result on a new line to standard output (stdout). If the key is not present in the cache, print -1.

## 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>