LRU Cache Implementation

Design and implement a data structure for the Least Recently Used (LRU) cache, which supports the following operations:

1. get(key) - Return the value associated with the key if it exists; otherwise, return -1.
2. put(key, value) - Insert the value into the cache if the key does not exist, or update the value if the key exists. If the cache reaches its capacity, remove the least recently used item before inserting a new item.

Input:

The first line contains two space-separated integers 'C' (capacity of the cache) and 'Q' (number of operations).
The next 'Q' lines contain operations. 
- If the operation type is 0, it is followed by an integer key for a get operation.
- If the operation type is 1, it is followed by two space-separated integers key and value for a put operation.

Output:

For each get operation (type 0), print the integer value associated with the key, or -1 if the key does not exist.

Example:

Input:

3 11
1 1 1
1 2 2
1 3 3
1 4 5
0 3
0 1
0 4
1 2 3
0 1
0 3
0 2

Output:

3
-1
5
-1
3
3

Constraints:

• 1 <= C <= 10⁴
• 1 <= Q <= 10⁵
• 1 <= key, value <= 10⁹
• Time Limit: 1 sec

Note:

You do not need to print anything; your function implementation will return results directly.