Implement an LRU cache with fixed capacity. Support get(key) and put(key, value) so that both run in O(1) average time, and evict the least recently used key when the cache is full.
1 <= capacity <= 30000 <= key <= 10^40 <= value <= 10^52 * 10^5 operations