You are given a positive integer $n$. Your task is to find any three integers $a$, $b$ and $c$ ($0 \le a, b, c \le 10^9$) for which $(a\oplus b)+(b\oplus c)+(a\oplus c)=n$, or determine that there are no such integers.

Here $a \oplus b$ denotes the bitwise XOR of $a$ and $b$. For example, $2 \oplus 4 = 6$ and $3 \oplus 1=2$.


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The following lines contain the descriptions of the test cases.

The only line of each test case contains a single integer $n$ ($1 \le n \le 10^9$).


-----Output-----

For each test case, print any three integers $a$, $b$ and $c$ ($0 \le a, b, c \le 10^9$) for which $(a\oplus b)+(b\oplus c)+(a\oplus c)=n$. If no such integers exist, print $-1$.


-----Examples-----

Input
5
4
1
12
2046
194723326
Output
3 3 1
-1
2 4 6
69 420 666
12345678 87654321 100000000


-----Note-----

In the first test case, $a=3$, $b=3$, $c=1$, so $(3 \oplus 3)+(3 \oplus 1) + (3 \oplus 1)=0+2+2=4$.

In the second test case, there are no solutions.

In the third test case, $(2 \oplus 4)+(4 \oplus 6) + (2 \oplus 6)=6+2+4=12$.

Difficulty: EASY
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
for n in [*map(int, open(0))][1:]:
	print(*((n // 2, 0, 0), [-1])[n % 2])


for n in [*map(int, open(0))][1:]:
	print(-(n % 2) or f'{n // 2} 0 0')


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	if n % 2:
		return [-1]
	else:
		a = b = 0
		c = n // 2
		return [a, b, c]
for _ in range(int(input())):
	print(*solve())


T = int(input())
q = []
for i in range(T):
	n = int(input())
	q.append(n)

def solve(n):
	if n & 1:
		print(-1)
	else:
		print(0, 0, n // 2)
for n in q:
	solve(n)


l = int(input())
ans = []
for i in range(l):
	n = int(input())
	if n % 2 != 0:
		ans.append('-1')
	else:
		ans.append('0 0 ' + str(int(n / 2)))
for line in ans:
	print(line)


def a():
	return int(input())

def kil_(n):
	if n % 2 != 0:
		return '-1'
	else:
		return '{0} {0} 0'.format(int(n / 2), int(n / 2), 0)

def kil(a):
	t = int(input())
	A = ''
	for i in range(t):
		A += kil_(a()) + '\n'
	print(A[:-1])
kil(a)


n = int(input())
arr = []
a = 0
try:
	while n > 0:
		string = int(input())
		if string:
			arr.append(string)
			n -= 1
except Exception:
	pass

def fnc(n, a):
	return a | int(n / 2)
for n in arr:
	if n % 2 != 0:
		print(-1)
	else:
		print('{} {} {}'.format(a, a, fnc(n, a)))


for x in [*map(int, open(0))][1:]:
	print(*((x // 2, 0, 0), [-1])[x % 2])


for _ in [*map(int, open(0))][1:]:
	print(*((_.__floordiv__(2), 0, 0), [-1])[_ % 2])


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	if n & 1:
		print(-1)
	else:
		print(n // 2, 0, 0)


import sys
inputs = sys.stdin.readlines()
for i in range(1, len(inputs)):
	n = int(inputs[i])
	if n % 2 == 1:
		sys.stdout.write('-1\n')
	else:
		sys.stdout.write(f'0 0 {n // 2}\n')


for p in [*map(int, open(0))][1:]:
	print(*((p // 2, 0, 0), [-1])[p % 2])


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = inp()
for _ in range(t):
	n = inp()
	if n % 2 != 0:
		pr('-1')
	else:
		print(n // 2, 0, 0)


for s in [*open(0)][1:]:
	n = int(s.split()[0])
	if n % 2 == 0:
		print(n // 2, n // 2, 0)
	else:
		print(-1)


t = int(input())
o = []
for jj in range(t):
	v = []
	n = int(input())
	if n % 2 == 0:
		o.append(str(n // 2) + ' ' + str(n // 2) + ' ' + str(0))
	else:
		o.append('-1')
for i in range(t):
	print(o[i])


for s in [*open(0)][1:]:
	s = int(s)
	print(*[[0, 0, s // 2], [-1]][s & 1])


import sys

def parse_next_line():
	test_str = sys.stdin.readline()
	return int(test_str)

def main(_):
	num_inputs = int(sys.stdin.readline())
	for _ in range(num_inputs):
		num = parse_next_line()
		if num % 2 != 0:
			print(-1)
		else:
			print(0, num // 2, num // 2)
main(sys.argv[1:])


n = int(input())
arr = []
for i in range(n):
	arr.append(int(input()))
for i in arr:
	if i % 2 == 0:
		print(i // 2, i // 2, 0)
	else:
		print(-1)


import sys
input = sys.stdin.readline
t = int(input())
for t in range(t):
	n = int(input())
	if n % 2 != 0:
		print(-1)
	else:
		a = 0
		b = n // 2
		c = n - b
		print(a, b, c)


for s in [*open(0)][1:]:
	s = int(s)
	print(-1) if s & 1 else print(0, s // 2, s // 2)


tc = int(input())
while tc > 0:
	n = int(input())
	ans = ''
	if bin(n)[-1] == '1':
		ans = '-1'
	else:
		n = n >> 1
		ans = '{} 0 0'.format(n)
	print(ans)
	tc = tc - 1


import sys
input = sys.stdin.readline

def sol():
	n = int(input())
	if n & 1:
		return [-1]
	return [0, n >> 1, n >> 1]
for _ in range(int(input())):
	print(*sol())


n = int(input())
li = []
for k in range(n):
	c = int(input())
	li.append(c)
for i in range(len(li)):
	if li[i] % 2 != 0:
		print('-1')
	else:
		p1 = p2 = li[i] / 2
		s = 0
		print(int(p1), int(p2), int(s))


def xr(n):
	if n % 2 != 0:
		return '-1'
	else:
		return str(n // 2) + ' ' + str(n // 2) + ' ' + str(0)
t = int(input())
while t:
	t -= 1
	n = int(input())
	print(xr(n))


for _ in range(int(input())):
	n = int(input())
	print('-1' if n % 2 == 1 else f'{0} {0} {n // 2}')


testcases = int(input())
for i in range(testcases):
	n = int(input())
	if n % 2 == 0:
		print(n // 2, n // 2, 0, sep=' ')
	else:
		print(-1)


for _ in range(int(input())):
	number = int(input())
	num = number
	if number % 2 == 0:
		print(f'0 0 {round(number / 2)}')
	else:
		print(-1)


for _ in range(int(input())):
	n = int(input())
	if n % 2:
		print(-1)
		continue
	print(0, 0, n // 2)


for i in range(int(input())):
	a = int(input())
	if a % 2 != 0:
		print('-1')
	else:
		print(f'0 0 {a // 2}')


test_number = int(input())
for k in range(test_number):
	number = int(input())
	if number % 2 == 0:
		output = [int(number / 2), int(number / 2), 0]
		print(' '.join(map(str, output)))
	else:
		print(-1)


iT = int(input())
for _ in range(iT):
	n = int(input())
	if n % 2 == 0:
		print('%s' % (n // 2) + ' 0 0')
	else:
		print('-1')


t = int(input())
for i in range(t):
	n = int(input())
	if n % 2 == 0:
		print(0, 0, n // 2)
	else:
		print(-1)


t = int(input())
while t:
	n = int(input())
	if n % 2 == 0:
		print(str(n // 2) + ' 0 ' + str(n // 2))
	else:
		print('-1')
	t = t - 1


t = int(input())
for i in range(t):
	x = int(input())
	if x % 2 == 1:
		print(-1)
	else:
		print('%d %d %d' % (0, x / 2, x / 2))


MAX = 10 ** 9 + 1

def solve():
	n = int(input())
	if n % 2 == 0:
		print(0, 0, n // 2)
	else:
		print(-1)
t = int(input())
for _ in range(t):
	solve()


test = int(input())
while test:
	n = int(input())
	if n % 2 == 0:
		print(0, 0, n // 2)
	else:
		print(-1)
	test -= 1


ncase = int(input())
for case in range(1, ncase + 1):
	n = int(input())
	if n % 2 == 1:
		ans = -1
	else:
		ans = f'{n // 2} 0 0'
	print(ans)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	if n % 2 == 1:
		print(-1)
	else:
		print(f'{n // 2} {n // 2} {0}')


t = int(input())
for _ in range(t):
	final = int(input())
	if final % 2 != 0:
		print('-1')
	else:
		half = str(final // 2)
		print('0 ' + half + ' ' + half)


t = int(input())
res = []
for _ in range(t):
	n = int(input())
	if n % 2 == 1:
		res.append(-1)
	else:
		res.append([n // 2, 0, 0])
for i in res:
	if isinstance(i, list):
		print(*i)
	else:
		print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	if n % 2 == 0:
		print('0' + ' ' + '0' + ' ' + str(n // 2))
	else:
		print(-1)


def xor(x):
	if x % 2 == 1:
		print(-1)
		return
	else:
		print(f'0 0 {int(x / 2)}')

def main():
	tests = int(input())
	for i in range(tests):
		n = int(input())
		xor(n)
main()


t = int(input())
while t != 0:
	a = int(input())
	if a % 2 == 0:
		print('0 0', int(a / 2))
	else:
		print('-1')
	t -= 1


x = int(input())
for i in range(x):
	number = int(input())
	if number % 2 == 0:
		target = int(number / 2)
		print(str(target) + ' ' + str(target) + ' 0')
	else:
		print('-1')


T = int(input())
for t in range(T):
	n = int(input())
	if n % 2 != 0:
		print(-1)
	else:
		m = int(n / 2)
		print(f'{m} {m} {0}')