Dragonado rarely gets stuck on a problem, unless of course, if it's a XOR Problem. 

Dragonado while coming back from the Fruit Market, finds an array A of N elements. He wants to find 4 integers, say i_{1},i_{2},i_{3} and i_{4}, such that:

\texttt{popcount}(A_{i_{1}} \oplus A_{i_{2}}) = \texttt{popcount}(A_{i_{3}} \oplus A_{i_{4}})
1 ≤ i_{1},i_{2},i_{3},i_{4} ≤ N  and   i_{1},i_{2},i_{3},i_{4}  are pairwise distinct. 

Here, \texttt{popcount}(x) denotes the number of set bits in the binary representation of x. Secondly, \oplus denotes the [bitwise XOR operation].

Can you help Dragonado find four integers i_{1}, i_{2}, i_{3} and i_{4} which satisfy the given conditions?

Output -1 if no answer exists.

If multiple answers exist, output any.

Note: The input of this problem is large, so use fast input/output methods.

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N - the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

------ Output Format ------ 

For each test case, output i_{1},i_{2},i_{3},i_{4} which satisfy the given conditions. 

Output -1 if no numbers satisfying the conditions exist.

------ Constraints ------ 

$1 ≤ T ≤ 10^{4}$
$4 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- It is guaranteed that sum of $N$ over all test cases does not exceed $2 \cdot 10^{6}$

----- Sample Input 1 ------ 
2
4
1 2 5 6
4
1 2 3 4

----- Sample Output 1 ------ 
1 4 2 3
-1
----- explanation 1 ------ 
Test case-1: $1, 4, 2, 3$ is a valid answer because:

- $\texttt{popcount}(A_{1} \oplus A_{4}) = \texttt{popcount}(7) = 3$
- $\texttt{popcount}(A_{2} \oplus A_{3}) = \texttt{popcount}(7) = 3$

Therefore, $\texttt{popcount}(A_{i_{1}} \oplus A_{i_{2}}) = \texttt{popcount}(A_{i_{3}} \oplus A_{i_{4}})$

Test case-2: We can prove that no $i_{1}, i_{2}, i_{3}, i_{4}$ exist that satisfy the given conditions.

Source: codechef | Difficulty: VERY_HARD
Tags: Mathematics

Complete search


Solutions:
import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p2 = [1]
for i in range(70):
	p2.append(p2[-1] * 2)
p = 10 ** 9 + 7
ANS = []
for t in range(int(input())):
	(n,) = ints()
	a = ints()
	inds = [i for i in range(n)]
	rn = 1000
	v = 0
	for i in range(rn):
		(p, q, r, s) = random.sample(inds, 4)
		x = a[p] ^ a[q]
		y = a[r] ^ a[s]
		(c1, c2) = (0, 0)
		while x:
			if x % 2:
				c1 += 1
			x //= 2
		while y:
			if y % 2:
				c2 += 1
			y //= 2
		if c1 == c2:
			v = 1
			break
	if v:
		print(p + 1, q + 1, r + 1, s + 1)
	else:
		print(-1)


import collections
from collections import defaultdict

def pop(x):
	return bin(x).count('1')

def fun():
	for i1 in range(n - 3):
		for i2 in range(i1 + 1, n - 2):
			for i3 in range(i2 + 1, n - 1):
				for i4 in range(i3 + 1, n):
					if pop(a[i1] ^ a[i2]) == pop(a[i3] ^ a[i4]):
						return [i1, i2, i3, i4]
					if pop(a[i1] ^ a[i3]) == pop(a[i2] ^ a[i4]):
						return [i1, i3, i2, i4]
					if pop(a[i1] ^ a[i4]) == pop(a[i3] ^ a[i2]):
						return [i1, i4, i3, i2]
	return -1
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if n >= 62:
		d = defaultdict(lambda : [])
		for i in range(0, n, 2):
			tmp = pop(a[i] ^ a[i + 1])
			d[tmp] += [i, i + 1]
			if len(d[tmp]) > 2:
				print(*[x + 1 for x in d[tmp]])
				break
	else:
		tmp = fun()
		if tmp == -1:
			print(-1)
		else:
			print(*[x + 1 for x in tmp])


co = lambda z: bin(z).count('1')

def bruteforce(n, a):
	for i in range(n):
		for j in range(n):
			for k in range(n):
				for l in range(n):
					net = set([i, j, k, l])
					if len(net) == 4:
						x = a[i] ^ a[j]
						y = a[k] ^ a[l]
						if co(x) == co(y):
							print(i + 1, j + 1, k + 1, l + 1)
							return
	print(-1)
	return

def solve(n, a):
	net = [-1] * 32
	for i in range(0, n - 1, 2):
		k = co(a[i] ^ a[i + 1])
		if net[k] != -1:
			print(i + 1, i + 2, net[k] + 1, net[k] + 2)
			return
		net[k] = i
for _ in range(int(input())):
	n = int(input())
	a = tuple(map(int, input().split()))
	if n <= 62:
		bruteforce(n, a)
	else:
		solve(n, a)


def brutef(A):
	c = 0
	for i in range(0, len(A)):
		for j in range(i + 1, len(A)):
			for k in range(i + 1, len(A)):
				if k == j:
					continue
				for l in range(k + 1, len(A)):
					if l == j:
						continue
					if bin(A[i] ^ A[j]).count('1') == bin(A[k] ^ A[l]).count('1'):
						c = 1
						print(i + 1, '', j + 1, '', k + 1, '', l + 1)
						break
				if c == 1:
					break
			if c == 1:
				break
		if c == 1:
			break
	if c != 1:
		print(-1)

def eff(A):
	v = []
	for i in range(31):
		v.append(-1)
	for i in range(0, len(A) - 1, 2):
		x = bin(A[i] ^ A[i + 1]).count('1')
		if v[x] != -1:
			print(v[x] + 1, '', v[x] + 2, '', i + 1, '', i + 2)
			break
		else:
			v[x] = i
T = int(input())
for cases in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	if N <= 64:
		brutef(A)
	else:
		eff(A)


def solve1(a):
	v = {}
	for i in range(0, len(a), 2):
		x = popcount(a[i] ^ a[i + 1])
		if x not in v:
			v[x] = [i, i + 1]
		elif x in v:
			print(v[x].pop(0) + 1, v[x].pop(0) + 1, i + 1, i + 2)
			return

def popcount(x):
	count = 0
	while x > 0:
		if x & 1 == 1:
			count = count + 1
		x = x >> 1
	return count

def solve2(a):
	n = len(a)
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(i + 1, n):
				if j == k:
					continue
				for l in range(k + 1, n):
					if j == l:
						continue
					if popcount(a[i] ^ a[j]) == popcount(a[k] ^ a[l]):
						print(i + 1, j + 1, k + 1, l + 1)
						return
	print(-1)
T = int(input())
for tc in range(T):
	n = int(input())
	a = list(map(int, input().split(' ')))
	solve2(a)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def setbit(x):
	ans = 0
	while x:
		x &= x - 1
		ans += 1
	return ans

def func():
	n = inp()
	sq = seq()
	n = min(n, 32)
	for i in range(n):
		for j in range(n):
			for k in range(n):
				for l in range(n):
					if len(set([i, j, k, l])) == 4:
						if setbit(sq[i] ^ sq[j]) == setbit(sq[k] ^ sq[l]):
							print(i + 1, j + 1, k + 1, l + 1)
							return
	print(-1)
t = inp()
for i in range(t):
	func()


def popc(n):
	c = 0
	while n > 0:
		c += 1
		n = n & n - 1
	return c
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if n >= 64:
		d = [[-1, -1] for i in range(31)]
		if n % 2 != 0:
			n = n - 1
		for i in range(0, n, 2):
			t = popc(l[i] ^ l[i + 1])
			if d[t] != [-1, -1]:
				print(d[t][0] + 1, d[t][1] + 1, i + 1, i + 2)
				break
			else:
				d[t] = [i, i + 1]
	else:
		ans = False
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(i + 1, n):
					if j == k:
						continue
					for m in range(i + 1, n):
						if m == k or m == j:
							continue
						t1 = popc(l[i] ^ l[j])
						t2 = popc(l[k] ^ l[m])
						if t1 == t2:
							print(i + 1, j + 1, k + 1, m + 1)
							ans = True
							break
					if ans:
						break
				if ans:
					break
			if ans:
				break
		if not ans:
			print(-1)