Find the Dominant Flower

This is an interactive problem.

You are given n flowers, each with a positive integer beauty value. It is guaranteed that there exists one flower whose beauty is at least twice the beauty of every other flower. Your task is to identify the index of this dominant flower.

You can ask at most k queries. In each query, you choose two indices i and j (1 ≤ i, j ≤ n) and the interactor returns the absolute difference between the beauty values of the i-th and the j-th flower.

When you have determined the answer, output it in the format: ! i, where i is the 1-indexed position of the dominant flower. Remember to flush the output buffer after each query and each answer.

Note: For the purpose of offline testing, the entire list of beauty values of the flowers will be provided after the parameters n and k for each test case.

The correctness condition for a candidate flower with beauty a is that for every other flower with beauty b, the following inequality holds:

\( a \ge 2 \times b \)

inputFormat

The input begins with an integer T (T ≥ 1) indicating the number of test cases. For each test case, the first line contains two positive integers n and k (the maximum number of allowed queries). The following line contains n positive integers representing the beauty values of the flowers.

This is an interactive problem; however, for offline testing the beauty values are provided directly.

outputFormat

For each test case, output a single line in the form ! i where i is the 1-indexed position of the dominant flower that satisfies the condition of being at least twice every other flower's beauty.

sample

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

! 3
! 1
! 4