You are given an integer $n$. Please find a ($0$-indexed) permutation $p$ of $0,1,\dots, n-1$, which satisfies that for each integer $i\in[0,n)$, $p_i\oplus i=p_i+i$.

Here $\oplus$ means bitwise exclusive-OR operation. Exclusive-OR (XOR) is a logical operation in Boolean algebra that outputs true only when the inputs differ (one is true and the other is false). In other words, XOR returns a true value if and only if the two input values are different. Here is a truth table for XOR.

A bitwise XOR is a binary operation that takes two bit patterns of equal length and performs the logical exclusive-OR operation on each pair of corresponding bits. For example: $0101$ (decimal $5$)$\oplus$ $0011$ (decimal $3$) $= 0110$ (decimal $6$).

Input

The first line contains an integer $n$ $(1\leq n\leq 10^6)$, denoting the length of the permutation.

Output

Output $n$ integers in one line, denoting $p_0, p_1,\dots,p_{n-1}$. If there is no such permutation, output $-1$ instead.

Examples

Input 1

3

Output 1

0 2 1