LRU Cache Implementation

Implement a Least Recently Used (LRU) Cache that supports two operations: put(key, value) and get(key). The cache is initialized with a fixed capacity. When a new key-value pair is inserted and the cache exceeds its capacity, the least recently used entry is removed.

The get operation returns the value associated with the key if it exists; otherwise, it returns -1. Accessing an existing key (via get or put) makes it the most recently used. Use the LRU eviction policy to ensure that the element which has not been used for the longest time is removed when necessary.

inputFormat

The input is read from stdin and consists of multiple lines:

• The first line contains an integer capacity ($1 \leq capacity \leq 10^5$) representing the capacity of the cache.
• Each subsequent line represents an operation in one of the following formats:
  • put key value — Insert or update the key with the given value.
  • get key — Retrieve the value of the given key.

The input continues until the end of file (EOF).

outputFormat

For each get operation, output the corresponding value on a separate line to stdout. If a key does not exist in the cache, output -1.

## sample

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