URI Online Judge | 1615

Insatisfaction on Elections

By Bruno Adami, Universidade de São Paulo - São Carlos BR Brazil

Timelimit: 1

An election was made in a small town of M citizens, where there were N candidates. People would write the candidate number in a piece of paper, and then they put it in a closed box.

At the end of the election, if a candidate receives a quantity strictly greater than 50% of the votes, he is considered the winner. Otherwise a second round of elections will happen.

As the manual counting process is very slow, you must write an algorithm that decides whose candidate is the winner or if none of them received enough votes and a second round is needed.


The first line contains an integer T (T ≤ 100) indicating the number of test cases.

For each test case, on the first line you will have the integers N (1 ≤ N ≤ 10) and M. On the following line, M (1 ≤ M ≤ 103* or 1 ≤ M ≤ 5*104**) integers will follow separated by spaces, indicating the candidate that each citizen voted for, it is, the number that was writen in each piece of paper inside the closed box.

*For around 90% of the cases;

**For the other cases.


For each test case, print the winning candidate, or -1 in the case of a second round of elections.

Sample Input Sample Output


2 3

1 1 2

2 5

1 2 2 1 2

3 4

1 2 3 1