Bitwise Equation CodeChef Solution

Problem

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

• 1≤�,�,�,�≤10181≤a,b,c,d≤1018
• $((a\&b)|c)\oplus d=N$

Here $\&$, $|$, and $\oplus$ represent bitwise AND, OR and XOR, respectively.

If there are multiple answers, print any of them. If no answer exists, print $-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$ 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

Sample 1:

3
1
2
3221225472

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

Explanation:

Test case $1$: We have $a=1$, $b=4$, $c=3$, $d=2$ and $((a\&b)|c)\oplus d=(0|3)\oplus 2=3\oplus 2=1.$

Test case $2$: We have $a=2$, $b=4$, $c=3$, $d=1$ and $((a\&b)|c)\oplus d=(0|3)\oplus 1=3\oplus 1=2.$

Test case $3$: Note that the value of $N$ might exceed the limit of signed a $32$-bit integer, use unsigned $32$-bit integers or $64$-bit integers instead.