Design an OOP LRU Cache

Problem: Design an OOP LRU Cache Design and implement an LRU (Least Recently Used) cache class LRUCache with the following operations: LRUCache(capacity): initialize the cache with maximum number of key-value pairs capacity. get(key): If key exists, return its value and mark it as most recently used. If key does not exist, return -1. put(key, value): If key exists, update its value and mark it as most recently used. If key does not exist, insert the pair. If the cache size exceeds capacity, evict the least recently used entry. Complexity Requirements Both get and put must run in O(1) time. Design Requirements (OOP) Show clear object-oriented design (e.g., Node class / DoublyLinkedList class / Cache class responsibilities). Do not use built-in ordered containers that directly solve LRU (e.g., Python OrderedDict, Java LinkedHashMap). I/O Format (for testing) Read from stdin: Line 1: integer capacity Line 2: integer q number of operations Next q lines: one operation per line: get key put key value Print one line per get operation. Constraints 1 <= capacity <= 1e5 1 <= q <= 2e5 key, value are within 32-bit signed integer range 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 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