정수 $n$이 주어집니다. 다음 조건을 만족하는 $0,1,\dots, n-1$의 ($0$-인덱스) 순열 $p$를 찾으세요: 모든 정수 $i\in[0,n)$에 대해 $p_i\oplus i = p_i + i$입니다.

여기서 $\oplus$는 비트별 배타적 논리합 연산을 의미합니다. 배타적 논리합(XOR)은 불 대수에서 두 입력이 다를 때(하나는 참, 다른 하나는 거짓)만 참을 출력하는 논리 연산입니다. 즉, XOR은 두 입력 값이 다를 때에만 참 값을 반환합니다. 다음은 XOR의 진리표입니다.

비트별 XOR은 동일한 길이의 두 비트 패턴을 받아 각 대응하는 비트 쌍에 대해 논리적 배타적 논리합 연산을 수행하는 이항 연산입니다. 예: $0101$ (십진수 $5$) $\oplus$ $0011$ (십진수 $3$) $= 0110$ (십진수 $6$).

입력

첫 번째 줄에 정수 $n$ $(1\leq n\leq 10^6)$이 주어집니다. 이는 순열의 길이를 나타냅니다.

출력

한 줄에 $n$개의 정수를 출력합니다. $p_0, p_1,\dots,p_{n-1}$을 의미합니다. 만약 그러한 순열이 존재하지 않는다면, $-1$을 출력합니다.

예제

입력 1

3

출력 1

0 2 1