Implement LRU Cache

Implement a Least Recently Used (LRU) Cache. The LRU cache should support two operations: get(key) and put(key, value).

The get operation retrieves the value corresponding to a key if it exists in the cache, otherwise it returns -1.

The put operation inserts a new key-value pair or updates an existing key’s value. When the number of keys exceeds the cache's capacity, the least recently used (LRU) key is evicted. An accessed key (by either get or put) is considered to become the most recently used.

For clarity, consider the LRU property expressed in LaTeX: \(\text{If } key_i \text{ is used before } key_j, \text{ then } key_i \text{ is more recently used than } key_j.\)

inputFormat

The first line contains two integers: capacity and n, representing the capacity of the cache and the number of operations, respectively.

Each of the following n lines describes an operation. An operation is provided in one of the following formats:

• PUT key value
• GET key

outputFormat

For each GET operation, output a single line with the resulting integer. No output is generated for PUT operations.

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