Implement an LRU Cache

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Problem

Implement an LRU (Least Recently Used) cache that supports:

LRUCache(capacity): initialize the cache with the given positive capacity.

get(key): return the value if the key exists and mark it as most recently used; otherwise return -1.

put(key, value): insert or update the key with the value and mark it as most recently used; if the cache exceeds capacity, evict the least recently used entry.

Requirements:

Target time complexity: O(1) per get/put.

Constraints

Number of operations: 1 <= N <= 2 * 10^5

key, value are 32-bit integers

Sample Tests

Input:

capacity=2

put(1,1)

put(2,2)

get(1)

put(3,3)

get(2)

put(4,4)

get(1)

get(3)

get(4)

Output:

1

-1

3

4

Input:

capacity=1

put(1,1)

put(2,2)

get(1)

get(2)

Output:

-1

2

Input:

capacity=2

put(1,1)

put(1,10)

get(1)

Output:

10

Input:

capacity=3

get(42)

Output:

-1

Input:

capacity=2

put(1,1)

put(2,2)

put(3,3)

get(1)

get(2)

get(3)

Output:

-1

2

3

Example

Input

capacity=2

put(1,1)

put(2,2)

get(1)

put(3,3)

get(2)

put(4,4)

get(1)

get(3)

get(4)

Output

1

-1

3

4

Complete solveLRUCacheOperations. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.