LFU Cache (wrapped variant)

Implement an LFU (Least Frequently Used) cache. When the cache reaches capacity, it must evict the key with the lowest frequency; if multiple keys share the same frequency, evict the least recently used (LRU) among them. Support operations: put(key, value): Insert/update a key-value pair. get(key): Return the value if present, otherwise return -1. Requirements: Average time complexity of get and put is O(1). If capacity == 0, all put operations have no effect and get always returns -1. Input format (stdin/stdout version) Line 1: integer capacity Line 2: integer n number of operations Next n lines: one operation per line: get key put key value Output format Print one line per get operation. Constraints 0 <= capacity <= 1e5 1 <= n <= 2e5 key, value are 32-bit signed integers Test cases Example Input 2 10 put 1 1 put 2 2 get 1 put 3 3 get 2 get 3 put 4 4 get 1 get 3 get 4 Output 1 -1 3 -1 3 4