問題文

正整数 $N$ について $M$ を $N$ のハミング重みとしたとき、 $N\oplus M=X$ となるような $N$ は存在するでしょうか。

厳密に述べましょう。

ハミング重みとは、整数を二進数表記にしたときに立っているビットの総数のことです。
例えば、 $5$ を二進数で表すと $101$ で、 $1$ が $2$ つあります。よって、 $5$ のハミング重みは $2$ となります。

また、ここで $A\oplus B$ は $A$ と $B$ のビットごとの排他的論理和を表します。

非負整数 $X$ が与えられます。正整数 $N$ とそのハミング重み $M$ に関して、 $N\oplus M$ が $X$ となる $N$ が存在するかを判定し、存在する場合は $N$ として考えられるものを $1$ つ示してください。

ただし、 $1\leq N\leq 2\times 10^{18}$ である必要があり、この制約下では $N\oplus M=X$ を満たす $N$ が存在する場合 $1\leq N\leq 2\times 10^{18}$ も満たす $N$ が存在することが証明できます。

入力

$X$

• $0\leq X\leq 10^{18}$
• $X$ は整数

出力

• $N$ のハミング重みを $M$ としたときに $N\oplus M=X$
• $1\leq N\leq 2\times 10^{18}$

上記 $2$ つの条件を満たす $N$ が存在しない場合 $-1$ と出力してください。

条件を満たす $N$ が存在する場合、 $N$ として考えられるものを $1$ つ出力してください。

条件を満たす $N$ が複数存在する場合、そのうちどれを出力しても構いません。

サンプル

3

2

15

-1

314159265358979

314159265359001