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, - . 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 1 st query of type 1 : We have 1>1 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 3rd query of type 1: We have 2>2 and 3>3 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. Jutput Format each query of type 1, print the space-separated values on a single Constraints 1N51041Q21051K21051value109