The Trade Desk's Kokai platform may cache frequently accessed computation results. Implement a cache simulator that supports both least recently used (LRU) and most recently used (MRU) eviction policies.
Create a function that processes put and get operations. Every successful get, and every put of an existing key, makes that key the most recently used. When inserting a new key into a full cache, evict the least recently used key for LRU, or the most recently used key for MRU.
Implement cache_results(capacity, policy, operations), where capacity is an integer, policy is either "LRU" or "MRU", and operations is a list of operations. Each operation is either ["put", key, value] or ["get", key]. Keys and values are integers or strings. Return a list containing the result of each get, using -1 for a missing key. Do not return results for put operations.
Each cache operation must run in constant time.
def cache_results(capacity, policy, operations):