LRU Cache Implementation

This problem requires you to implement a data structure that simulates a basic caching system using the Least Recently Used (LRU) policy. The cache supports two operations:

• PUT key value: Inserts the key-value pair into the cache. If the key already exists, update its value, and mark it as most recently used. If the cache is full, evict the least recently used item before inserting the new one.
• GET key: Retrieves the value associated with key if it exists in the cache; otherwise, returns -1. The accessed key should be marked as most recently used.

The input is provided via standard input, and the output from all GET operations should be printed on standard output, one per line.

You must use \( \LaTeX \) for any formulas. For example, the capacity is given by \( C \) and the number of operations by \( n \).

inputFormat

The first line contains two integers ( C ) and ( n ), where ( C ) is the capacity of the cache and ( n ) is the number of operations. Each of the following ( n ) lines contains an operation in one of the following formats:

• "PUT key value" : Insert or update the key with its corresponding value.
• "GET key" : Retrieve the value associated with the key and print it.

Only GET operations produce output. All input is from standard input (stdin).

outputFormat

For each GET operation, output the value associated with the specified key, or -1 if the key is not present in the cache. Each result should be printed on a new line to standard output (stdout).## 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