There are N numbers written on a blackboard. 

In one operation, Chef can:
Choose any 3 integers A, B, and  C written on the blackboard.
Erase them from the blackboard.
Write A \oplus B, B \oplus C, and C \oplus A on the blackboard. Here, \oplus denotes the [bitwise XOR operation].

Your task is to make all the numbers written on the blackboard equal to 0 using at most 11111 operations.

It is guaranteed that all the numbers on the blackboard can be made 0 under the given constraints.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains a single integer N, the number of integers written on the blackboard.
- Next line contains N space separated integers A_{1}, A_{2}, \dots A_{N}, the integers written on the blackboard initially.

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

For each test case:
- On the first line, output M (0 ≤ M ≤ 11111) - the number of operations you are going to perform.
- Next M lines contain 3 space-separated integers A, B, and C (A, B, C should be present on the blackboard at the time of operation ) - denoting the integers using which operation is performed.

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

$1 ≤ T ≤ 10$
$6 ≤ N ≤ 1000$
$0 ≤ A_{i} ≤ 10^{9}$

----- Sample Input 1 ------ 
1
6
0 1 2 3 2 0
----- Sample Output 1 ------ 
2
2 3 2
1 1 1

----- explanation 1 ------ 
Test case $1$: We can make all the numbers $0$ using $2$ operations:
- Operation $1$: Choose the integers $2, 3,$ and $2$ and replace them with $2\oplus 3 = 1, 3\oplus 2 = 1,$ and $2\oplus 2 = 0$. Thus, numbers on the blackboard are now $[0, 1, 0, 1, 1, 0]$.
- Operation $2$: Choose the integers $1, 1,$ and $1$ and replace them with $1\oplus 1 = 0, 1\oplus 1 = 0,$ and $1\oplus 1 = 0$. Thus all numbers on the blackboard are now $0$.

Difficulty: HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
operations = []
nOps = 0

def operate(x, y, z):
	operations.append([arr[x], arr[y], arr[z]])
	global nOps
	nOps += 1
	(arr[x], arr[y], arr[z]) = (arr[x] ^ arr[y], arr[y] ^ arr[z], arr[z] ^ arr[x])
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	operations = []

	def operate(x, y, z):
		operations.append([arr[x], arr[y], arr[z]])
		(arr[x], arr[y], arr[z]) = (arr[x] ^ arr[y], arr[y] ^ arr[z], arr[z] ^ arr[x])
	for bit in range(30, -1, -1):
		idx = []
		for i in range(n):
			if arr[i] >> bit & 1:
				idx.append(i)
			if len(idx) == 3:
				operate(idx[0], idx[1], idx[2])
				idx = []
		if len(idx) == 1:
			x = idx[0]
			(y, z, w) = ((i + 1) % n, (i + 2) % n, (i + 3) % n)
			operate(x, y, z)
			operate(y, z, w)
			operate(x, y, z)
		elif len(idx) == 2:
			x = idx[0]
			nxt = []
			for i in range(1, 4):
				ii = (x + i) % n
				if ii != idx[1]:
					nxt.append(ii)
			y = idx[1]
			(z, w) = (nxt[0], nxt[1])
			operate(y, z, w)
			operate(x, y, w)
	print(len(operations))
	for op in operations:
		print('%d %d %d' % (op[0], op[1], op[2]))


powers = [2 ** i for i in range(43)]

def binarToDec(a):
	ans = 0
	for i in range(len(a)):
		ans += a[i] * powers[i]
	return ans
for lkdk in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	ans = []
	for i in a:
		x = bin(i)[2:]
		x = x.zfill(35)
		b.append(list(x))
	for i in range(35):
		(zero, one) = ([], [])
		for j in range(n):
			if b[j][i] == '0':
				zero.append(j)
			else:
				one.append(j)
		while len(one) >= 3:
			ab = one.pop()
			bc = one.pop()
			cd = one.pop()
			zero.append(ab)
			zero.append(bc)
			zero.append(cd)
			ans.append((a[ab], a[bc], a[cd]))
			x1 = a[ab] ^ a[bc]
			x2 = a[bc] ^ a[cd]
			x3 = a[cd] ^ a[ab]
			a[ab] = x1
			a[bc] = x2
			a[cd] = x3
			b[ab] = list(bin(x1)[2:].zfill(35))
			b[bc] = list(bin(x2)[2:].zfill(35))
			b[cd] = list(bin(x3)[2:].zfill(35))
		if len(one) == 1:
			ab = one.pop()
			bc = zero.pop()
			cd = zero.pop()
			ans.append((a[ab], a[bc], a[cd]))
			x1 = a[ab] ^ a[bc]
			x2 = a[cd] ^ a[ab]
			x3 = a[bc] ^ a[cd]
			a[ab] = x1
			a[bc] = x2
			a[cd] = x3
			b[ab] = list(bin(x1)[2:].zfill(35))
			b[bc] = list(bin(x2)[2:].zfill(35))
			b[cd] = list(bin(x3)[2:].zfill(35))
			zero.append(cd)
			one.append(bc)
			one.append(ab)
		if len(one) == 2:
			ab = one.pop()
			bc = zero.pop()
			cd = zero.pop()
			ans.append((a[ab], a[bc], a[cd]))
			x1 = a[ab] ^ a[bc]
			x2 = a[cd] ^ a[ab]
			x3 = a[bc] ^ a[cd]
			a[ab] = x1
			a[bc] = x2
			a[cd] = x3
			b[ab] = list(bin(x1)[2:].zfill(35))
			b[bc] = list(bin(x2)[2:].zfill(35))
			b[cd] = list(bin(x3)[2:].zfill(35))
			zero.append(cd)
			one.append(bc)
			one.append(ab)
		if len(one) == 3:
			ab = one.pop()
			bc = one.pop()
			cd = one.pop()
			zero.append(ab)
			zero.append(bc)
			zero.append(cd)
			ans.append((a[ab], a[bc], a[cd]))
			x1 = a[ab] ^ a[bc]
			x2 = a[bc] ^ a[cd]
			x3 = a[cd] ^ a[ab]
			a[ab] = x1
			a[bc] = x2
			a[cd] = x3
			b[ab] = list(bin(x1)[2:].zfill(35))
			b[bc] = list(bin(x2)[2:].zfill(35))
			b[cd] = list(bin(x3)[2:].zfill(35))
	print(len(ans))
	for i in ans:
		print(*i)


import queue
import collections
import sys
mod7 = 1000000007
diff4 = [[0, 1], [1, 0], [0, -1], [-1, 0]]
dir4 = ['R', 'D', 'L', 'U']
revdir4 = ['L', 'U', 'R', 'D']
local = False

def fastinp():
	return sys.stdin.readline().strip()

def fastout(str):
	sys.stdout.writeline(str)

def getarr(_type=int):
	return [_type(x) for x in fastinp().split()]

def getint():
	return int(fastinp())

def initarr_2d(row, col, defval=0):
	return [[defval for i in range(0, col)] for j in range(0, row)]

def grid_check(i, j, n, m):
	return i >= 0 and j >= 0 and (i < n) and (j < m)
t = getint()
for i in range(t):
	n = getint()
	a = getarr()
	oper = []

	def dooper(ix, iy, iz):
		x = a[ix]
		y = a[iy]
		z = a[iz]
		oper.append([x, y, z])
		a[ix] = x ^ y
		a[iy] = z ^ y
		a[iz] = x ^ z
	for b in range(30, -1, -1):
		idx = []
		for i in range(0, n):
			if a[i] >> b & 1 == 1:
				idx.append(i)
			if len(idx) == 3:
				dooper(idx[0], idx[1], idx[2])
				idx = []
		if len(idx) > 0:
			idx0 = []
			ii = idx[0]
			for d in range(0, 6):
				curi = (ii + d) % n
				if curi not in idx:
					idx0.append(curi)
			if len(idx) == 1:
				ix = idx0[0]
				iy = idx0[1]
				iz = idx0[2]
				dooper(ii, ix, iy)
				dooper(ii, ix, iz)
				dooper(ii, iy, iz)
			if len(idx) == 2:
				ij = idx[1]
				ix = idx0[1]
				iy = idx0[2]
				dooper(ij, ix, iy)
				dooper(ii, ij, iy)
	print(len(oper))
	for l in oper:
		print(l[0], l[1], l[2])