LRU Cache Simulation

This problem requires you to simulate an implementation of an LRU (Least Recently Used) Cache. The cache has a fixed capacity, denoted by \( C \), and supports two operations:

• put key value: Insert a new key-value pair into the cache or update an existing key's value. If the cache reaches its capacity, the least recently used item should be evicted.
• get key: Retrieve the value of the specified key if it exists; otherwise, output -1. Accessing a key will mark it as recently used.

Your task is to process a sequence of these commands given via standard input and print the results of all get operations to standard output.

All formulas are represented in \( \LaTeX \) format. For example, the capacity is represented as \( C \) and the number of commands as \( N \).

inputFormat

The first line of input contains two integers, \( C \) (the capacity of the cache) and \( N \) (the number of commands).

Each of the following \( N \) lines contains a command, which is either:

• put key value: Insert or update the key with the given value.
• get key: Retrieve the value of the given key.

outputFormat

For each get command in the input, output the result on a new line to standard output. If the key does not exist, print -1.

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