LRU Cache Task Description

Design and implement a data structure for a Least Recently Used (LRU) cache to support two operations:

1. get(key) - Returns the value for the given key if it exists in the cache, otherwise returns -1.
2. put(key, value) - Inserts the key-value pair into the cache if the key is not present. If the key is present, updates the value. When the cache exceeds its capacity, it should remove the least recently used item before inserting the new one.

Input:

The first line contains two space-separated integers, 'C' and 'Q', which denote the cache's capacity and the number of operations respectively.
 The next 'Q' lines contain operations, each line starting with an integer indicating the type of operation.
 If it is 0, it is a get operation followed by an integer key.
 If it is 1, it is a put operation followed by two space-separated integers key and value.

Output:

For every operation of type 0, output an integer. If the key exists, print its value; otherwise, print -1.

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
5
3

Explanation:

The cache is initialized with a capacity of 3. As operations are performed, the state changes accordingly by inserting, updating, or retrieving elements.

Constraints:

• 1 <= C <= 10^4
• 1 <= Q <= 10^5
• 1 <= key, value <= 10^9
• Time Limit: 1 sec

Note:

You do not need to implement printing functionality, just complete the specified function.