Most Frequent Product in Time Windows

In this problem, you are given (T) test cases. For each test case, you are provided with a sequence of product orders and a set of queries. Each query specifies a time window given by two indices (L) and (R) (1-indexed). Your task is to determine the product ID that occurs most frequently within the window ( [L, R] ). In the event of a tie, choose the smallest product ID among those with the highest frequency.

Input Format: The first line contains an integer (T), the number of test cases. For each test case, the first line contains two integers (N) and (Q), representing the number of orders and the number of queries, respectively. The second line contains (N) space-separated integers representing the product orders. Each of the next (Q) lines contains two integers (L) and (R), representing a query.

Output Format: For each query in all test cases, output the most frequent product ID on a new line.

inputFormat

The input starts with an integer (T) (the number of test cases). For each test case, the first line contains two integers (N) and (Q). The second line contains (N) integers denoting the product IDs in the order they were ordered. Each of the following (Q) lines contains two integers (L) and (R), indicating the range of the query (1-indexed).

outputFormat

For each query across all test cases, print the product ID that occurs most frequently within the range. If there is more than one such product, print the smallest one. Each output should be on a new line.## sample

2
10 3
1 1 2 2 3 3 4 4 4 4
1 5
2 8
4 10
7 2
1 2 2 3 3 3 1
2 5
1 7

1
2
4
2
3