Вам дано целое положительное целое число \(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\).
5 4 1 12 2046 194723326
3 3 1 -1 2 4 6 69 420 666 12345678 87654321 100000000
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач