Chef has an array A of length N such that A_{i} = i.

In one operation, Chef can pick any two elements of the array, delete them from A, and append either their [bitwise XOR] or their [bitwise OR] to A.

Note that after each operation, the length of the array decreases by 1.

Let F be the final number obtained after N-1 operations are made. You are given an integer X, determine if you can get F=X via some sequence of operations.

In case it is possible to get F = X, print the operations too (see the section Output format for more details), otherwise print -1.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single line containing two space-separated integers N and X.

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

For each test case, output -1 if it is impossible to get X in the end.
Otherwise print N-1 lines denoting the operations.

On each line, print
- 1\ x\ y if you want replace x and y with x\ OR\ y.
- 2\ x\ y if you want replace x and y with x\ XOR\ y.

Note that x and y are the elements of the array at the time of applying the operation, and if either of them is not present in the array you will receive a WA verdict.

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

$1 ≤ T ≤ 5000$
$2 ≤ N ≤ 2^{15}$
$1 ≤ X ≤ 2^{16} - 1$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
3 2
2 2
4 7

----- Sample Output 1 ------ 
2 1 3
1 2 2
-1
1 1 2
1 3 3
1 3 4

----- explanation 1 ------ 
Test case $1$: The operations are as follows:
- Initially, the array is $A = [1, 2, 3]$
- The first move removes $1$ and $3$ and appends their $XOR$, making the array $A = [2, 2]$
- The second move removes $2$ and $2$ and appends their $OR$, making the array $A = [2]$

Test case $2$: It can be shown that no sequence of operations can achieve $F = 2$ in this case.

Test case $3$: The operations are as follows:
- Initially, the array is $A = [1, 2, 3, 4]$
- After the first move, the array is $A = [3, 4, 3]$
- After the second move, the array is $A = [4, 3]$
- After the third move, the array is $A = [7]$

Source: codechef | Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics

Constructive algorithms


Solutions:
from collections import Counter

def main():
	(n, x) = map(int, input().split())
	if n == 2 and x == 2:
		print(-1)
		return
	if n == 2 and x == 3:
		print(1, 1, 2)
		return
	nb = bin(n)[2:]
	xb = bin(x)[2:]
	if len(xb) > len(nb):
		print(-1)
		return
	if len(nb) > len(xb):
		if nb[1:] == '0' * (len(nb) - 1):
			print(-1)
			return
	st_pow = set()
	i = 1
	while i <= n:
		st_pow.add(i)
		i *= 2
	curr = 3
	for i in range(4, n + 1):
		if i not in st_pow:
			print(1, curr, i)
			curr |= i
	xb = xb[::-1]
	for i in range(len(xb)):
		p = pow(2, i)
		if xb[i] == '0':
			print(2, curr, p)
			st_pow.remove(p)
			curr ^= p
		else:
			print(1, curr, p)
			st_pow.remove(p)
			curr |= p
	if len(st_pow) > 0:
		a = list(st_pow)
		for z in a:
			print(2, curr, z)
			curr ^= z
	return
for _ in range(int(input())):
	main()


from collections import *
import bisect
tc = int(input())
for _ in range(1, 1 + tc):
	(n, x) = list(map(int, input().split()))
	bk = 0
	for i in range(20, 0, -1):
		if n & 1 << i > 0:
			bk = 1 << i + 1
			break
	if x >= bk:
		print(-1)
		continue
	if n & n - 1 == 0 and x & n == 0:
		print(-1)
		continue
	if n == 2:
		if x == 3:
			print('1 1 2')
		else:
			print(-1)
		continue
	s1 = [x for x in range(1, n + 1)]
	s2 = []
	for i in range(20):
		if 1 << i > n:
			break
		if 1 << i & x == 0:
			s1.remove(1 << i)
			s2.append(1 << i)
	(orAns, xorAns) = (0, 0)
	n = len(s1)
	if n > 0:
		orAns = s1.pop(0)
		n -= 1
		while n > 0:
			val = s1.pop(0)
			print(f'1 {orAns} {val}')
			orAns |= val
			n -= 1
		bisect.insort(s2, orAns)
	m = len(s2)
	if m > 0:
		xorAns = s2.pop(0)
		m -= 1
		while m > 0:
			val = s2.pop(0)
			print(f'2 {xorAns} {val}')
			xorAns |= val
			m -= 1


import fileinput

def is_solvable_old(a, b):
	if b.bit_length() > a.bit_length():
		return False
	msp = 1 << a.bit_length() - 1
	if a == msp and b & msp == 0:
		return False
	if a == 2 and b == 2:
		return False
	return True

def is_p2(a):
	return a == 1 << a.bit_length() - 1

def solve(target, n):
	if n == 2:
		if target == 3:
			print('1 1 2')
		else:
			print('-1')
		return
	if is_p2(n):
		if n & target == 0:
			print('-1')
			return
	if n.bit_length() < target.bit_length():
		print('-1')
		return
	accumulator = 3
	for i in range(5, n + 1):
		if is_p2(i):
			continue
		print(f'1 {accumulator} {i}')
		accumulator = accumulator | i
	extractor = 1
	for i in range(1, n.bit_length() + 1):
		if extractor & target > 0:
			print(f'1 {accumulator} {extractor}')
		else:
			print(f'2 {accumulator} {extractor}')
			accumulator ^= extractor
		extractor = extractor << 1

def solveBad(target, n, xmap):
	print(f'solve {target}, {n}')
	msp = 1 << n.bit_length() - 1
	print(f'msp is {msp}')
	buffer = msp
	if n == 1:
		if target == 0:
			print(f'2 1 {xmap[1]}')
		elif target == 1:
			print(f'1 1 {xmap[1]}')
		else:
			raise ValueError('unexpected')
	for j in range(msp + 1, n):
		print(f'1 {buffer} {j}')
		buffer = buffer | j
	if target & msp == 0:
		print(f'2 {buffer} {n}')
		buffer = buffer ^ n
		print(f'1 {buffer} {buffer}')
	else:
		print(f'1 {buffer} {n}')
		buffer = buffer | n
		consumer = buffer ^ msp
		print(f'1 {buffer} {consumer}')
		target = target ^ msp
	print(f'consumer {consumer}, target {target}')
	xmap[consumer]
	solve(target, msp - 1, xmap)
with fileinput.input() as f:
	t = int(f.readline().strip())
	for i in range(t):
		(a, b) = [int(e) for e in f.readline().strip().split(' ', 1)]
		solve(b, a)


import sys

def solve():
	(n, x) = map(int, sys.stdin.readline().split())
	maxNum = 0
	for i in range(20, 0, -1):
		if n & 1 << i:
			maxNum = 1 << i + 1
			break
	if n == 2 and x != 3 or x >= maxNum or (n & n - 1 == 0 and x & n == 0):
		print('-1')
		return
	if n == 2:
		print('1 1 2')
		return
	arr1 = set()
	for i in range(1, n + 1):
		arr1.add(i)
	arr2 = set()
	for i in range(0, 21):
		num = 1 << i
		if num > n:
			break
		if x & num == 0:
			arr1.remove(num)
			arr2.add(num)
	num = 0
	if len(arr1) > 0:
		num = arr1.pop()
		for i in arr1:
			print('1 ' + str(num) + ' ' + str(i))
			num = num | i
	comp = 0
	if len(arr2) > 0:
		comp = arr2.pop()
		for i in arr2:
			print('1 ' + str(comp) + ' ' + str(i))
			comp = comp | i
	if num > 0 and comp > 0:
		print('2 ' + str(num) + ' ' + str(comp))
t = int(input()) or 1
while t:
	solve()
	t -= 1


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	d = dict.fromkeys(list(range(1, n + 1)))
	if n == 2:
		if x == 3:
			print('1 1 2')
		else:
			print(-1)
	else:
		for i in range(20):
			ni = 1 << i
			d[ni] = True
			if ni & n:
				msbn = i
			if ni & x:
				msbx = i
		if msbx > msbn:
			print(-1)
		elif not d[n] or x & n:
			val = 0
			for i in range(1, n + 1):
				if not d[i]:
					if i > 3:
						print('1 {} {}'.format(i, val))
					val |= i
			for i in d.keys():
				if i > n or not d[i]:
					continue
				if x & i:
					print('1 {} {}'.format(i, val))
					val |= i
				else:
					print('2 {} {}'.format(i, val))
					val ^= i
		else:
			print(-1)