Implement a Least Recently Used (LRU) cache that supports the following operations:
- PUT key value — Insert or update the value for the key. If inserting causes the cache to exceed its capacity, evict the least recently used key before inserting.
- GET key — Return the value for the key if it exists, otherwise return
-1. A successful GET counts as a "use" of that key.
Both operations must run in O(1) average time.
Input format
Line 1: two space-separated integers capacity ops where capacity is the maximum number of key-value pairs the cache can hold, and ops is the number of operations that follow.
Lines 2 to ops+1: one operation per line in one of two forms:
PUT key value(key and value are integers)GET key
Output format
For each GET operation, print a single line containing the returned value (the integer value, or -1 if not found). PUT operations produce no output.
Constraints
- 1 ≤ capacity ≤ 100,000
- 1 ≤ ops ≤ 200,000
- 0 ≤ key, value ≤ 10^6