Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. The Third Three Number Problem

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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$$$.

Example

Input

541122046194723326

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$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/07/2023 21:38:06 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|