Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

• LFUCache(int capacity)
• int get(int key) — return value or -1.
• void put(int key, int value) — insert/update. If over capacity, evict the least frequently used key. Ties broken by LRU.

All operations must run in O(1).

Example:

Input: capacity=2, put(1,1), put(2,2), get(1)→1, put(3,3), get(2)→-1, get(3)→3, put(4,4), get(1)→1, get(3)→3, get(4)→4

Constraints: 0 <= capacity <= 10^4