LRU Cache Implementation

You are required to implement a Least Recently Used (LRU) Cache. The cache should support two operations:

• get(key): Return the value associated with the key if it exists in the cache; otherwise, return -1.
• put(key, value): Insert or update the key with its value. If the cache is at capacity, it should remove the least recently used item before adding the new one.

Both operations should ideally be performed in O(1) time complexity. In formal notation, if the cache capacity is \( C \) and you perform \( Q \) operations, your implementation should handle each operation in constant time on average.

For example, consider the following sequence of operations with a cache capacity of 2:

put(1, 1)
put(2, 2)
get(1)    // returns 1, cache becomes {2=2, 1=1}
put(3, 3) // evicts key 2, cache becomes {1=1, 3=3}
get(2)    // returns -1 (not found)
put(4, 4) // evicts key 1, cache becomes {3=3, 4=4}
get(1)    // returns -1 (not found)
get(3)    // returns 3
get(4)    // returns 4

Implement the LRU Cache and process a sequence of operations provided via standard input. Output the result of every get operation to standard output.

inputFormat

The first line contains two integers:

1. capacity \(C\) — the maximum number of items the cache can hold.
2. n — the number of operations to perform.

The next n lines each describe an operation in one of the following forms:

• put key value — insert or update the key with the given value.
• get key — retrieve the value associated with the key.

All keys and values are integers.

outputFormat

For each get operation, output the result (the value associated with the key, or -1 if the key does not exist) on a separate line.

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