Problem

Given an integer N, find four positive distinct integers a, b, c and d such that:

Table of Contents

1≤a,b,c,d≤10181≤a,b,c,d≤1018
((a&b)∣c)⊕d=N

Here &&, ∣∣, and ⊕⊕ represent bitwise AND, OR and XOR, respectively.

If there are multiple answers, print any of them. If no answer exists, print −1−1.

Input Format

The first line of input will contain a single integer T, denoting the number of test cases.
Each test case consists of one line of input, containing a single integer �N.

Output Format

For each test case, output −1−1 if there is no way to find four distinct integers to satisfy the equation.

Otherwise, print on a new line any four space-separated integers a, b, c and d that satisfy the conditions.

Constraints

1≤T≤1041≤T≤104
0≤N<2320≤N<232

Sample 1:

Input

Output

1 4 3 2
2 4 3 1
920426639 955944413 754668683 4244364431

Explanation:

Test case 11: We have a=1, b=4, c=3, d=2 and ((a&b)∣c)⊕d=(0∣3)⊕2=3⊕2=1.

Test case 22: We have a=2, b=4, c=3, d=1 and((a&b)∣c)⊕d=(0∣3)⊕1=3⊕1=2.

Test case 33: Note that the value of N might exceed the limit of signed a 3232-bit integer, use unsigned 3232-bit integers or 6464-bit integers instead.

Solution:

click on below image to get all solution link

solution