Implement LRU Cache

You are given a cache with a fixed capacity and a series of operations to perform. Your task is to 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.
• put(key, value): Insert or update the key-value pair in the cache. If inserting a new key causes the cache to exceed its capacity, evict the least recently used key.

The cache operates under the following constraints:

• \(1 \leq capacity \leq 10^4\)
• \(1 \leq key, value \leq 10^5\)
• At most \(10^5\) operations will be performed.

Note: Each time a key is accessed (via get or put), it is considered the most recently used.

inputFormat

The input is read from stdin and has the following format:

C Q
op1
op2
...
opQ

Where:

• C is an integer representing the capacity of the LRU Cache.
• Q is the number of operations.
• Each of the next Q lines represents an operation in one of the following forms:
• put key value
• get key

For every get operation, your program should output the returned result on a new line.

outputFormat

For each get operation, print the resulting integer to stdout on a separate line.

## sample

3 9
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4

1
2
-1
3
4

</p>