Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if it exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if it exists. Otherwise, add the key-value pair. If the number of keys exceeds the capacity, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input:
2
put 1 1
put 2 2
get 1
put 3 3
get 2
put 4 4
get 1
get 3
get 4
Output:
1
-1
1
3
4

Constraints:

• 1 ≤ capacity ≤ 3000
• 0 ≤ key ≤ 10⁴
• 0 ≤ value ≤ 10⁵
• At most 2 × 10⁵ calls will be made to get and put

Input format: First line: capacity. Subsequent lines: either get key or put key value.

Output format: One line per get call with its return value.