Implement an LRU Cache

Problem: Implement an LRU Cache Implement an LRU (Least Recently Used) cache supporting the following operations: get key: If key exists in the cache, output its value and mark the key as most recently used. Otherwise, output -1. put key value: Insert or update a key-value pair. If key already exists, update its value and mark it as most recently used. If key does not exist and the cache is full, evict the least recently used key-value pair before inserting the new one. Both get and put must run in O(1) average time. Input Format The first line contains an integer capacity. The second line contains an integer q, the number of operations. Each of the next q lines is one of: get key put key value Output Format For every get operation, print its result on a separate line. Constraints 0 <= capacity <= 10^5 1 <= q <= 2 * 10^5 0 <= key, value <= 10^9 Example Input 2 9 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4 Output 1 -1 -1 3 4 Example Input 2 9 put 1 1 put 2 2 get 1 put 3 3 get 2 put 4 4 get 1 get 3 get 4 Output 1 -1 -1 3 4