Background

Third Heart.

Problem Description

mikage likes construction problems. One day, she came up with a simple construction problem:

Given $a$, try to construct a quadruple of positive integers $(a,b,c,d)$ such that:

1. $\sqrt{a^2+b^2+c^2+d^2}=a\oplus b\oplus c\oplus d$.
2. $a<b<c<d<2^{63}$.

If there is no solution, output $-1$. Here, $\oplus$ denotes bitwise XOR in binary.

Input Format

One line containing one integer $a$.

Output Format

If there is a solution, output three integers $b,c,d$ in one line separated by spaces. If there is no solution, output $-1$.

31

172 484 632

Hint

Sample Explanation

As stated in the problem.

Constraints

This problem uses bundled subtasks. You can get the score of a subtask only if you pass all testdata points in that subtask.

For all data, $1\le a \le 10^9$.

Special Property A: There exists an integer $k\ge 2$ such that $a = 2^k$.

Special Property B: $a \equiv 0 \pmod{4}$.

Special Property C: $a \equiv 1 \pmod{4}$.

Special Property D: There exists an integer $k\ge 2$ such that $a = 2^k-1$.

Translated by ChatGPT 5