题目描述

给定一个正整数 $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$。

说明/提示

在第一个测试用例中，$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$。

由 ChatGPT 4.1 翻译

样例

5
4
1
12
2046
194723326

3 3 1
-1
2 4 6
69 420 666
12345678 87654321 100000000