LRU Cache Implementation

You are required to implement a Least Recently Used (LRU) Cache which supports two operations: get and put.

The LRU cache should work as follows:

• get(key): Returns the value associated with the key if the key exists in the cache; otherwise returns -1.
• put(key, value): Inserts the value if the key is not already present. If the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item. If the key already exists, update its value and mark it as recently used.

The cache is defined by its capacity \( C \) (where \( C \geq 1 \)). The order of usage is updated when a key is accessed via get or updated/inserted via put. The least recently used element is the one that has not been accessed for the longest period.

Example:

Input:
2
7
put 1 1
put 2 2
get 1      # returns 1 (accessing key 1 makes it most recently used)
put 3 3   # evicts key 2 since it is the least recently used
get 2      # returns -1 (not found)
put 4 4   # evicts key 1
get 1      # returns -1
Output:
1
-1
-1

</p>

inputFormat

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

1. The first line contains an integer \( C \), the capacity of the cache.
2. The second line contains an integer \( N \), the number of commands.
3. The following \( N \) lines each contain a command. A command is either:
• put key value - Insert or update the key with the given value.
• get key - Retrieve the value for the given key.

outputFormat

For every get command, output the corresponding value on a separate line to standard output. If a key is not found, output -1.

## sample

2
7
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1

1
-1
-1

</p>