LRU Cache III

Design and implement a data structure for a Least Recently Used (LRU) cache. It should support two operations:

• get(key) → returns the value associated with key if it exists in the cache; otherwise returns -1.
• put(key, value) → inserts the key-value pair if the key is not present, or updates its value if it already exists. When the cache is at its capacity limit and a new key needs to be inserted, the least recently accessed key must be evicted.

The cache is initialized with a fixed positive integer capacity.

Both get and put must run in O(1) average time complexity.

Input Format (custom stdin)

• The first line contains an integer capacity.
• The second line contains an integer q, the total number of operations.
• Each of the next q lines describes one operation:
  • get key
  • put key value

Output Format

For every get operation, print the returned value on a new line.

Constraints

• 1 <= capacity <= 1e5
• 1 <= q <= 2e5
• key and value are 32-bit integers.

Example

Input:

2
8
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3

Output:

1
-1
-1
3

Explanation:

• After put(1,1) and put(2,2), the cache holds {1:1, 2:2} (capacity 2).
• get(1) returns 1 and marks key 1 as most recently used.
• put(3,3) evicts key 2 (the least recently used) and inserts {1:1, 3:3}.
• get(2) returns -1 because key 2 was evicted.
• put(4,4) evicts key 1 and inserts {3:3, 4:4}.
• get(1) returns -1 (evicted).
• get(3) returns 3.