Cache it You need to implement the Least Frequently Used (LFU) cache with the capacity N. You are also given Q operations of the following type: - 1, key, 1 : Get the value of the key from the cache. If the value does not exist in the cache return 1. - 2, key, value: Update the value of the key if present, or insert the key if not already present. When the cache reaches its capacity, it should]invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), smallest key should be removed. Task For each operation of type 1, print the required value. Example Assumption N: 2 Q: 6 Operations: [(2,1,1),(2,2,2),(1,1,1),(2,3,3),(1,2,1),(1,1,1)] Approach During the 1st query of type 1 : We have 11 and 22 in the cache. So, for query (1,1,1) we get the value 1. During the 2nd query of type 1 : We have 22 and 33 in the Explanation Given - N: 2 - Q. 5 - Operations: [(1,2,1),(2,1,3),(2,2,4),(2,4,5),(1,2,1)] Approach - During the 1 st operation of type 1: The cache is empty. So, for query (1,2, -1) we get the value 1 - During the 2 nd operation of type 2 : We have 13 in the cache. - During the 3rd operation of type 2 : We have 13 and 24 in the cache. - During the 4 th operation of type 2: We have 24 and 45 in the cache. Since the frequency of key 1 and key 2 was the same, key 1 was removed. - During the 5 th operation of type 1: We get a value 4. Approarh - During the 1 st query of type 1 . We have 11 and 2>2 in the cache. So, for query (1,1,1) we get the value 1 - During the 2 nd query of type 1: We have 2>2 and 3>3 in the cache, So, for query (1,2,1) we get the value 2 . - During the 3 rd query of type 1 : We have 22 and 33 in the cache. So, for query (1,1,1) we get the value 1, since 1 is not found in the cache. Function description Complete the function Solve(). This function takes the following parameters and returns the required array of results: - N : Represents the capacity of the cache - Q : Represents the number of operations on the cache. - operations: Represents the operations on the cache. Input Format Note: This is the input format that you must use to provide custom input (available above the Compile and Test button). - The first line contains N - the capacity of the cache. - The next line contains Q - number of operations on the cache. - The next Q lines contain 3 space-separated integers. Output Format For each query of type 1, print the space-separated values on a single line