Design a Recency-Eviction Cache

Implement a fixed-capacity key-value cache that removes the least recently used entry when it becomes full. Support the following operations: - `get(key)`: Return the value associated with `key` if it exists; otherwise return `-1`. Accessing a key marks it as recently used. - `put(key, value)`: Insert or update the value for `key`. If the cache is already at capacity and the key does not exist, evict the least recently used key before inserting the new one. Updating an existing key should also mark it as recently used. Requirements: - Cache capacity is a positive integer provided at initialization. - Both `get` and `put` should run in average `O(1)` time. - You may assume keys are unique integers and values are integers. Example: - Capacity = 2 - `put(1, 10)` - `put(2, 20)` - `get(1)` returns `10` - `put(3, 30)` evicts key `2` - `get(2)` returns `-1` - `put(4, 40)` evicts key `1` - `get(1)` returns `-1` - `get(3)` returns `30` - `get(4)` returns `40`