Chef has a circular sequence $A$ of $N$ non-negative integers $A_1, A_2, \ldots, A_N$ where $A_i$ and $A_{i+1}$ are considered adjacent, and elements $A_1$ and $A_N$ are considered adjacent.
An operation on position $p$ in array $A$ is defined as replacing $A_p$ by the bitwise OR of elements adjacent to $A_p$. Formally, an operation is defined as:
- If $p = 1$, replace $A_1$ with $A_N | A_{2}$
- If $1 < p < N$, replace $A_p$ with $A_{p-1} | A_{p+1}$
- If $p = N$, replace $A_N$ with $A_{N-1} | A_1$
Here, '|' denotes the bitwise OR operation.
Now, Chef must apply operations at each position exactly once, but he may apply the operations in any order.
Being a friend of Chef, you are required to find a sequence of operations, such that after applying all the $N$ operations, the bitwise OR of the resulting array is $K$, or determine that no such sequence of operations exist.

-----Input:-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$ denoting the number of elements, and the required bitwise OR after operations.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output:-----
For each test case, if no valid sequence of operations exist, print -1.
Otherwise, print $N$ space-separated integers in which $i$-th integer denote the position chosen in the $i$-th operation. If there are multiple valid sequences of operations, you may print any valid sequence.

-----Constraints-----
- $1 \le T \le 10^5$
- $3 \le N \le 2*10^5$
- $0 \le A_i, K \le 10^9$
- It's guaranteed that the total length of the arrays in one test file doesn't exceed $10^6$

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

-----Sample Output:-----
2 1 3
-1
-1
-1
2 3 1

-----Explanation:-----
In the first test case, initially, the sequence is {2, 1, 6}. 
- Chef applies the operation on the $2^{nd}$ index, so the sequence converts to {2, 6, 6}.
- Next, Chef applies the operation on the $1^{st}$ index, so the sequence converts to {6, 6, 6}.
- Next, Chef applies the operation on the $3^{rd}$ index, and this time sequence does not change.
The final sequence is {6, 6, 6}, and bitwise OR of this sequence is $6$ that is equal to given $K$.

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics

Constructive algorithms


Solutions:
def check():
	pref = [0] * n
	pref[0] = a[0]
	suff = [0] * n
	suff[-1] = a[-1]
	for i in range(1, n):
		pref[i] = pref[i - 1] | a[i]
		suff[n - i - 1] = suff[n - i] | a[n - i - 1]
	if suff[1] == k:
		return 0
	elif pref[n - 2] == k:
		return n - 1
	else:
		for i in range(1, n - 1):
			if pref[i - 1] | suff[i + 1] == k:
				return i
		return -1
for z in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	(ans, arr) = ([], [0] * n)
	for i in range(n):
		if k | a[i] != k:
			a[i] = a[i - 1] | a[(i + 1) % n]
			ans.append(i + 1)
			arr[i] = 1
	x = 0
	count = 0
	for i in range(n):
		x |= a[i]
	if x != k:
		print(-1)
	else:
		y = check()
		if y == -1:
			print(-1)
		else:
			for i in range(y, n + y):
				if arr[i % n] == 0:
					arr[i % n] == 1
					ans.append(i % n + 1)
			print(*ans)


tests = int(input())
for _ in range(tests):
	(n, k) = [int(j) for j in input().split()]
	nums = [int(j) for j in input().split()]
	check = [j - (j & k) != 0 for j in nums]
	impossible = check[0] and check[-1]
	for i in range(n - 1):
		impossible = impossible or (check[i] and check[i + 1])
	if impossible:
		print(-1)
	elif sum(check) != 0:
		start = -1
		for i in range(-1, n - 1):
			if check[i]:
				nums[i] = nums[i - 1] | nums[i + 1]
				if start == -1:
					start = i + 1
		for i in range(start, start + n):
			if not check[i % n]:
				nums[i % n] = nums[(i - 1) % n] | nums[(i + 1) % n]
		answer = 0
		for i in range(n):
			answer = answer | nums[i]
		if answer == k:
			for i in range(n):
				if check[i]:
					print(i + 1, end=' ')
			for i in range(start, start + n):
				if not check[i % n]:
					print(i % n + 1, end=' ')
			print('')
		else:
			print(-1)
	else:
		for i in range(-1, n - 1):
			if nums[i] == nums[i] & (nums[i - 1] | nums[i + 1]):
				for j in range(i, i + n):
					nums[j % n] = nums[(j - 1) % n] | nums[(j + 1) % n]
				answer = 0
				for j in range(n):
					answer = answer | nums[j]
				if answer == k:
					for j in range(i, i + n):
						print((j + n) % n + 1, end=' ')
					print('')
				else:
					print(-1)
				impossible = True
				break
		if not impossible:
			for i in range(n):
				ss = list(nums)
				for j in range(i, i + n):
					ss[j % n] = ss[(j + 1) % n] | ss[(j - 1) % n]
				answer = 0
				for j in range(n):
					answer = answer | ss[j]
				if answer == k:
					for j in range(i, i + n):
						print(j % n + 1, end=' ')
					print('')
					impossible = True
					break
		if not impossible:
			print(-1)