Design a cache with a fixed capacity that evicts the least frequently used key when it is full. If several keys are tied for the lowest use count, evict the one that was used least recently among them. Every get that finds a key and every put counts as a use of that key. get key returns the value or -1; put key value stores or updates the key. You are given a list of operations, and both operations should run in O(1) time.
Input
Line 1: the capacity and q, the number of operations. Next q lines: put k v or get k.
Output
For every get print the value, or -1, one per line.
Constraints
1 <= capacity <= 1000 1 <= q <= 10^4 1 <= k <= 10^4, 1 <= v <= 10^9
2 9 put 1 1 put 2 2 get 1 put 3 3 get 2 get 3 put 4 4 get 1 get 3
1 -1 3 -1 3
Adding 3 evicts key 2 (used once, versus twice for key 1); adding 4 evicts key 1, which ties with 3 on count but is older.