LRU Cache Implementation

Implement an LRU (Least Recently Used) cache that supports two operations: get and put.

The cache has a fixed capacity. When inserting a new item and the cache is full, it should remove the least recently used item before inserting the new item.

• get(key): Returns the value associated with the key if it exists in the cache; otherwise, returns -1.
• put(key, value): Inserts a new value or updates an existing value. If the key exists, its value should be updated and it becomes the most recently used. If the key does not exist and the cache is full, remove the least recently used entry before adding the new key-value pair.

For example, given an LRU cache with capacity \(C = 2\):

put 1 1
put 2 2
get 1    // returns 1
put 3 3 // evicts key 2
get 2    // returns -1 (not found)
put 4 4 // evicts key 1
get 1    // returns -1 (not found)
get 3    // returns 3
get 4    // returns 4

Your program will receive a series of commands from standard input. For each get command, output the result to standard output.

inputFormat

The first line of input contains an integer representing the capacity of the cache. The second line contains an integer (n) denoting the number of operations. Each of the following (n) lines contains a command in one of the following formats:

• put key value: Insert a key with its corresponding value into the cache, or update the value if the key already exists.
• get key: Retrieve the value associated with the key. If the key does not exist in the cache, return -1.

For every get command, output the result on a new line.

outputFormat

For each get operation in the input, output a single line containing the returned value from the cache. If the key is not present, the output should be -1.## sample

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

1
-1