Most Frequent Product Query

You are given T test cases. In each test case, there are N products (represented by integers) and Q queries. For each query, you are provided with a range [l, r] (1-indexed) corresponding to a subsequence of the click events. Your task is to determine the product that appears most frequently in the specified range. If there is a tie, choose the product with the smallest numerical value.

The decision criterion can be represented in LaTeX format as follows:

[ result = \min\left{ p \mid p = \arg\max_{p'} , \text{count}(p') \right} ]

Here, (\text{count}(p)) is the frequency of product (p) in the given range.

inputFormat

The input begins with an integer T, the number of test cases. For each test case, the first line contains two space-separated integers N and Q. The second line contains N space-separated integers representing the products clicked by users. Each of the following Q lines contains two space-separated integers l and r, which specify the 1-indexed range for the query.

outputFormat

For each query, output a single line containing the most frequently clicked product in the corresponding subsequence. In the event of a tie, output the smallest product identifier.## sample

1
10 2
3 1 2 2 3 3 4 4 4 1
1 5
2 10

2
4