← Home
write a go solution for Description:
Lisa was kidnapped by martians! It okay, because she has watched a lot of TV shows about aliens, so she knows what awaits her. Let's call integer martian if it is a non-negative integer and strictly less than 2^k, for example, when k=12, the numbers 51, 1960, 0 are martian, and the numbers pi, -1, 21/8, 4096 are not.

The aliens will give Lisa n martian numbers a_1,a_2,ldots,a_n. Then they will ask her to name any martian number x. After that, Lisa will select a pair of numbers a_i,a_j (ineqj) in the given sequence and count (a_ioplusx)&(a_joplusx). The operation oplus means Bitwise exclusive OR, the operation & means Bitwise And. For example, (5oplus17)&(23oplus17)=(00101_2oplus10001_2)&(10111_2oplus10001_2)=10100_2&00110_2=00100_2=4.

Lisa is sure that the higher the calculated value, the higher her chances of returning home. Help the girl choose such i,j,x that maximize the calculated value.

Input Format:
The first line contains an integer t (1<=t<=10^4) — number of testcases.

Each testcase is described by two lines.

The first line contains integers n,k (2<=n<=2*10^5, 1<=k<=30) — the length of the sequence of martian numbers and the value of k.

The second line contains n integers a_1,a_2,ldots,a_n (0<=a_i<2^k) — a sequence of martian numbers.

It is guaranteed that the sum of n over all testcases does not exceed 2*10^5.

Output Format:
For each testcase, print three integers i,j,x (1<=i,j<=n, ineqj, 0<=x<2^k). The value of (a_ioplusx)&(a_joplusx) should be the maximum possible.

If there are several solutions, you can print any one.

Note:
First testcase: (3oplus14)&(1oplus14)=(0011_2oplus1110_2)&(0001_2oplus1110_2)=1101_2=1101_2&1111_2=1101_2=13.

Second testcase: (1oplus0)&(1oplus0)=1.

Third testcase: (9oplus4082)&(13oplus4082)=4091.

Fourth testcase: (3oplus7)&(0oplus7)=4.. Output only the code with no comments, explanation, or additional text.