Implement LFU Cache

Problem: Implement an LFU (Least Frequently Used) Cache Design and implement an LFU cache that supports: get(key): return the value if present; otherwise return -1. put(key, value): write/update the key-value pair. If capacity is 0, do nothing. When the cache reaches capacity and you insert a new key, evict according to: Evict the key with the lowest frequency. If multiple keys share the same lowest frequency, evict the least recently used among them. Notes: Calling get on a key, or calling put on an existing key (update) counts as an access and increases its frequency by 1. Performance requirement Average time complexity of get and put must be O(1). Input format (operation sequence) First line: capacity m. Next m lines: either get key put key value Output Print one line per get operation. Constraints 0 <= capacity <= 1e5 1 <= m <= 2e5 key, value fit in 32-bit signed int Sample Tests Input: 2 6 put 1 1 put 2 2 get 1 put 3 3 get 2 get 3 Output: 1 -1 3 Input: 1 4 put 2 1 get 2 put 3 2 get 2 Output: 1 -1 Input: 0 3 put 1 1 get 1 put 2 2 Output: -1 Input: 2 7 put 1 10 put 2 20 get 1 get 2 put 3 30 get 1 get 3 Output: 10 20 10 30 Input: 2 9 put 1 1 put 2 2 get 1 get 1 put 3 3 get 2 get 3 get 1 get 3 Output: 1 1 -1 3 1 3 Example Input 2 6 put 1 1 put 2 2 get 1 put 3 3 get 2 get 3 Output 1 -1 3