给你一个正整数$$$n$$$。您的任务是找到任意三个整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ ($$$0 \le a, b, c \le 10^9$$$),其中 $$$(a\oplus b)+(b\oplus c)+(a\oplus c)=n$$$,或者确定不存在这样的整数。
这里 $$$a \oplus b$$$ 表示 $$$a$$$ 和 $$$b$$$ 的按位异或。例如,$$$2 \oplus 4 = 6$$$ 和 $$$3 \oplus 1=2$$$。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。以下行包含测试用例的描述。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^9$$$)。
输出
对于每个测试用例,打印任意三个整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ ($$$0 \le a, b, c \le 10^9$$$),其中 $$$(a\oplus b)+(b\oplus c)+(a\oplus c)=n$$$。如果不存在这样的整数,则打印 $$$-1$$$。
示例
输入 #1
5 4 1 12 2046 194723326
输出 #1
3 3 1 -1 2 4 6 69 420 666 12345678 87654321 100000000
注意
在第一个测试用例中,$$$a=3$$$、$$$b=3$$$、$$$c=1$$$,因此$$$(3 \oplus 3)+(3 \oplus 1) + (3 \oplus 1)=0+2+2=4$$$。
在第二个测试用例中,没有解决方案。
在第三个测试用例中,$$$(2 \oplus 4)+(4 \oplus 6) + (2 \oplus 6)=6+2+4=12$$$。