Implement an LRU Cache

Implement an LRU (Least Recently Used) cache that supports the following operations with O(1) average time: get(key): Return the value if key exists in the cache; otherwise return -1. put(key, value): Update the value if key exists; otherwise insert the key-value pair. If insertion causes the cache size to exceed capacity, evict the least recently used key. Requirements: Initialize as LRUCache(capacity) where capacity is a positive integer. Any key accessed by get or put becomes the most recently used. Constraints (typical interview-scale): 1 <= capacity <= 1e5 1 <= N <= 2e5 operations key and value are 32-bit integers I/O format (for the tests in this prompt) stdin: Line 1: integer capacity Line 2: integer q (# of operations) Next q lines: get key or put key value stdout: Print one line per get result. Example Input: 2 6 put 1 1 put 2 2 get 1 put 3 3 get 2 get 3 Output: 1 -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