Cache Operations Problem

You are provided with a cache that can hold a maximum of 'N' elements. Initially, this cache is empty. There are two main operations you can perform on this cache:

Explanation:

• Operation 1: [1 'U_ID' 'VAL'] - This operation signifies either inserting or updating an element in the cache. If the item with the 'U_ID' is already in the cache, update its value with 'VAL'. If it's not present and the cache has space, insert the element. If it's not present and the cache is full, remove the least frequently used item and insert the new element. In the case where multiple items are the least frequently used, remove the least recently used.
• Operation 2: [2 'U_ID'] - This operation is to retrieve the value associated with 'U_ID' from the cache. If it exists, return the value; otherwise, return -1.

Your task is to execute 'M' operations on the cache and return a list containing the results of all type 2 operations in the order they were performed.

Input:

The first line contains an integer ‘T’ representing the number of test cases.
Each test case starts with a line containing two integers, ‘N’ (cache size) and ‘M’ (number of operations).
The following ‘M’ lines detail the operations to be performed on the cache, either of type 1 or 2.

Output:

For each test case, return a list with the results of all type 2 operations in the order they were executed.

Example:

Given a cache capacity of 2, perform the following:
- Operation 1 2 3: Insert 'U_ID' 2 with value 3 into the cache.
- Operation 1 2 1: Update 'U_ID' 2 with value 1.
- Operation 2 2: Return value of 'U_ID' 2, which is 1.
- Operation 2 1: Return value of 'U_ID' 1, which is -1 as it's not in the cache.
- Operation 1 1 5: Insert 'U_ID' 1 with value 5.
- Operation 1 6 4: Cache is full, remove least freq. 'U_ID' 1 (used once), insert 'U_ID' 6 with value 4.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 1000
• 1 ≤ U_ID ≤ 10³
• 1 ≤ VAL ≤ 10⁶

Note:

All operations are valid, and printing is handled. Implement the function to return the list correctly.