There are 4 arrays of data. The arrays cat[n] and cnt[n] are each of n integers, and cat[i] relates to cnt[i]. These represent a category and count at each index. There are also two arrays of integers that represent q queries. The arrays l[q] and r[q] contain 1-based indices for the left and right ends of subarrays to consider in cat and cnt.

Process the queries in order. Create an array of q values where answer i relates to query i.

For each query i :

After all queries are processed, return the answer array.

Example 1 :

Input: cat = [1, 2, 1, 1, 3], cnt = [5, 3, 4, 5, 2], l = [1, 1], r = [3, 5]
Output: [8, 7]
Explanation:
For the first query, the subarrays are cat[1..3] = [1, 2, 1] and cnt[1..3] = [5, 3, 4].
The maximum count for each category is 5 for category 1 and 3 for category 2. The sum of these maxima is 5 + 3 = 8. The cnt values in the range are cleared to [0, 0, 0, 5, 2].
For the second query, the subarrays are cat[1..5] = [1, 2, 1, 1, 3] and cnt[1..5] = [0, 0, 0, 5, 2].
The maximum count for each category is 5 for category 1 and 2 for category 3. The sum of these maxima is 5 + 2 = 7. The cnt values in the range are cleared to [0, 0, 0, 0, 0].
The answer array is [8, 7].