Problem: Given an integer N, find two permutations:

  1. Permutation p of numbers from 1 to N such that pi ≠ i and pi & i = 0 for all i = 1, 2, ..., N. 
  2. Permutation q of numbers from 1 to N such that qi ≠ i and qi & i ≠ 0 for all i = 1, 2, ..., N. 



& is the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

Input

The input consists of one line containing a single integer N (1 ≤ N ≤ 105).

Output

For each subtask, if the required permutation doesn't exist, output a single line containing the word "NO"; otherwise output the word "YES" in the first line and N elements of the permutation, separated by spaces, in the second line. If there are several possible permutations in a subtask, output any of them.

Examples

Input

3


Output

NO
NO


Input

6


Output

YES
6 5 4 3 2 1 
YES
3 6 2 5 1 4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
template <class T, class U>
inline void Max(T &a, U b) {
  if (a < b) a = b;
}
template <class T, class U>
inline void Min(T &a, U b) {
  if (a > b) a = b;
}
inline void add(int &a, int b) {
  a += b;
  while (a >= 1000000007) a -= 1000000007;
}
int pow(int a, int b) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = ans * (long long)a % 1000000007;
    a = (long long)a * a % 1000000007;
    b >>= 1;
  }
  return ans;
}
int a[200010], b[20];
void cal(int n) {
  int K = n, m = 0;
  while (n) b[m++] = n & 1, n >>= 1;
  n = K;
  int l = 1 << m - 1, r = (1 << m) - 1;
  for (int i = m - 1 - 1; i >= 0; i--) {
    if (b[i]) {
      K = (1 << i) - 1;
      for (int j = 0; j < K + 1; j++) {
        int first = l + j, second = r - first;
        a[first] = second;
        a[second] = first;
      }
      l += 1 << i;
    }
  }
  a[l] = r - l;
  a[r - l] = l;
  if (r - l == 0) {
    puts("NO");
    return;
  }
  for (int i = m - 1 - 1; i >= 0; i--) {
    r = (1 << i + 1) - 1;
    for (int j = 1; j < (1 << i); j++) {
      if (!a[j] && !a[r - j]) {
        a[j] = r - j;
        a[r - j] = j;
      }
    }
  }
  for (int i = 1; i < n + 1; i++)
    if (!a[i]) {
      puts("NO");
      return;
    }
  puts("YES");
  for (int i = 1; i < n + 1; i++) {
    printf("%d ", a[i]);
  }
  puts("");
}
void cal1(int n) {
  for (int i = 1; i < n + 1; i++) a[i] = 0;
  int K = n, m = 0;
  while (n) b[m++] = n & 1, n >>= 1;
  n = K;
  K = 1 << m - 1;
  if (n == K || n <= 3) {
    puts("NO");
    return;
  }
  if (n > K + 1) {
    a[K] = K + 2;
    for (int i = K + 2; i < n; i++) a[i] = i + 1;
    a[n] = K;
    a[K + 1] = 1;
    a[1] = K + 1;
    for (int i = 2; i < K; i++) a[i] = i + 1, a[i + 1] = i, i++;
  } else {
    a[K] = K + 1, a[K + 1] = K;
    if (K == 4 || K == 2) {
      puts("NO");
      return;
    }
    K--;
    a[1] = K;
    a[K] = 1;
    a[2] = K - 1, a[3] = 2, a[K - 1] = 3;
    for (int i = 4; i < K - 1; i++) a[i] = i + 1, a[i + 1] = i, i++;
  }
  puts("YES");
  for (int i = 1; i < n + 1; i++) {
    printf("%d ", a[i]);
  }
}
int main() {
  int j, i, k, T, ca = 0, K = 0, m = 0, n;
  scanf("%d", &n);
  K = n;
  cal(n);
  cal1(n);
  return 0;
}