Design an LRU Cache

Design an LRU Cache Implement an LRU (Least Recently Used) cache that supports the following operations with O(1) average time complexity: LRUCache(capacity): Initialize the cache with a positive integer capacity. get(key): Return the value of key if it exists in the cache; otherwise return -1. put(key, value): If key exists, update its value and mark it as most recently used. If it does not exist, insert the key-value pair. If insertion causes the cache size to exceed capacity, evict the least recently used entry. I/O Format (for this prompt) Input: Line 1: integer capacity Line 2: integer n (number of operations) Next n lines: one operation per line: get key put key value Output: Print one line per get operation. Constraints 1 <= capacity <= 10^5 1 <= n <= 2*10^5 key and value are within 32-bit integer range Test Cases Case 1 Input: 2 8 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 Output: 1 -1 -1 3 Case 2 Input: 1 6 put 1 10 get 1 put 2 20 get 1 get 2 get 3 Output: 10 -1 20 -1 Case 3 Input: 3 7 put 1 1 put 2 2 put 3 3 get 2 put 4 4 get 1 get 3 Output: 2 -1 3 Case 4 Input: 2 6 get 10 put 10 5 get 10 put 11 6 put 12 7 get 11 Output: -1 5 -1 Case 5 Input: 2 5 put 1 1 put 1 2 get 1 put 2 2 get 2 Output: 2 2 Example Input 2 8 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 Output 1 -1 -1 3