Build an LRU Cache

Problem

Implement an LRU (Least Recently Used) cache with O(1) `get` and `put`. Used by every web browser, CDN, and database query planner.

Input

First line: capacity. Following lines: operations (`get k` or `put k v`). End with `END`.

Output

Print results of each `get` (or -1 if miss). Ignore `put` return.

Constraints

1 ≤ capacity ≤ 10^4, up to 10^5 operations

Sample input

2
put 1 1
put 2 2
get 1
put 3 3
get 2
END

Sample output

1
-1

Explanation

Cache capacity 2. put(1,1), put(2,2). get(1) → 1 (1 becomes most recent). put(3,3) evicts 2. get(2) → -1.

hash-maplinked-listdesignoop@Google@Uber@Meta

Visible test cases

in: 2
put 1 1
put 2 2
get 1
put 3 3
get 2
END

out: 1
-1

Your solution — run it, use AI if stuck

python