Implement LRU Cache with Time Limit

Implement a Least Recently Used (LRU) cache that supports the following operations, with each cache item having a specific time-to-live (TTL). put(key, value, ttl) - Add a cache item with the given key, value, and ttl (time-to-live in seconds). If the cache reaches capacity, evict the least recently used item or items that have expired. get(key) - Return the value of the item stored by key, or -1 if the key does not exist or the item has expired. Assume the cache has a capacity of capacity. The function signature is as follows: class LRUCache: def __init__(self, capacity: int): # Initialize def get(self, key: int) -> int: # Get cache item def put(self, key: int, value: int, ttl: int) -> None: # Add cache item Example: Input: capacity = 2 put(1, 1, 5) put(2, 2, 10) get(1) put(3, 3, 15) get(2) put(4, 4, 2) get(1) get(3) get(4) Output: 1 -1 -1 3 4 Example Input capacity = 2 put(1, 1, 5) put(2, 2, 10) get(1) put(3, 3, 15) get(2) put(4, 4, 2) get(1) get(3) get(4)