#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
template <class T1, class T2, class T3>
inline void gn(T1 &x1, T2 &x2, T3 &x3) {
  gn(x1), gn(x2), gn(x3);
}
template <class T1, class T2, class T3, class T4>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  gn(x1), gn(x2), gn(x3), gn(x4);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T1, class T2>
inline void print(T1 x1, T2 x2) {
  printsp(x1), println(x2);
}
template <class T1, class T2, class T3>
inline void print(T1 x1, T2 x2, T3 x3) {
  printsp(x1), printsp(x2), println(x3);
}
template <class T1, class T2, class T3, class T4>
inline void print(T1 x1, T2 x2, T3 x3, T4 x4) {
  printsp(x1), printsp(x2), printsp(x3), println(x4);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int p[100010], f[100010];
void aa(int n) {
  if (n == 0) return;
  int u = 1 << 31 - (__builtin_clz(n)), i;
  for (i = 0; i <= n - u; i++) {
    p[u + i] = u - i - 1;
    p[u - i - 1] = u + i;
  }
  aa(u - i - 1);
}
void bb(int n) {
  if (n == 3) return;
  int u = 1 << 31 - (__builtin_clz(n)), m = 0;
  if (u == 4) {
    f[m++] = 4;
    for (int i = 6; i <= n; i++) {
      f[m++] = i;
    }
  } else
    for (int i = u; i <= n; i++) {
      f[m++] = i;
    }
  for (int i = 1; i < m; i++) {
    p[f[i]] = f[i - 1];
  }
  p[f[0]] = f[m - 1];
  bb(u - 1);
}
int main() {
  int n;
  gn(n);
  if (n & 1)
    puts("NO");
  else {
    puts("YES");
    aa(n);
    for (int i = 1; i <= n; i++) {
      printsp(p[i]);
    }
    puts("");
  }
  if (n < 6 or (__builtin_popcount(n)) == 1)
    puts("NO");
  else {
    puts("YES");
    p[1] = 5, p[5] = 1, p[2] = 3, p[3] = 2;
    bb(n);
    for (int i = 1; i <= n; i++) {
      printsp(p[i]);
    }
    puts("");
  }
}

### Prompt

Please create a solution in Cpp to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
inline void smin(T &a, U b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, U b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
template <class T1, class T2, class T3>
inline void gn(T1 &x1, T2 &x2, T3 &x3) {
  gn(x1), gn(x2), gn(x3);
}
template <class T1, class T2, class T3, class T4>
inline void gn(T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  gn(x1), gn(x2), gn(x3), gn(x4);
}
template <class T>
inline void print(T first) {
  if (first < 0) {
    putchar('-');
    return print(-first);
  }
  if (first < 10) {
    putchar('0' + first);
    return;
  }
  print(first / 10);
  putchar(first % 10 + '0');
}
template <class T>
inline void printsp(T first) {
  print(first);
  putchar(' ');
}
template <class T>
inline void println(T first) {
  print(first);
  putchar('\n');
}
template <class T1, class T2>
inline void print(T1 x1, T2 x2) {
  printsp(x1), println(x2);
}
template <class T1, class T2, class T3>
inline void print(T1 x1, T2 x2, T3 x3) {
  printsp(x1), printsp(x2), println(x3);
}
template <class T1, class T2, class T3, class T4>
inline void print(T1 x1, T2 x2, T3 x3, T4 x4) {
  printsp(x1), printsp(x2), printsp(x3), println(x4);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
int p[100010], f[100010];
void aa(int n) {
  if (n == 0) return;
  int u = 1 << 31 - (__builtin_clz(n)), i;
  for (i = 0; i <= n - u; i++) {
    p[u + i] = u - i - 1;
    p[u - i - 1] = u + i;
  }
  aa(u - i - 1);
}
void bb(int n) {
  if (n == 3) return;
  int u = 1 << 31 - (__builtin_clz(n)), m = 0;
  if (u == 4) {
    f[m++] = 4;
    for (int i = 6; i <= n; i++) {
      f[m++] = i;
    }
  } else
    for (int i = u; i <= n; i++) {
      f[m++] = i;
    }
  for (int i = 1; i < m; i++) {
    p[f[i]] = f[i - 1];
  }
  p[f[0]] = f[m - 1];
  bb(u - 1);
}
int main() {
  int n;
  gn(n);
  if (n & 1)
    puts("NO");
  else {
    puts("YES");
    aa(n);
    for (int i = 1; i <= n; i++) {
      printsp(p[i]);
    }
    puts("");
  }
  if (n < 6 or (__builtin_popcount(n)) == 1)
    puts("NO");
  else {
    puts("YES");
    p[1] = 5, p[5] = 1, p[2] = 3, p[3] = 2;
    bb(n);
    for (int i = 1; i <= n; i++) {
      printsp(p[i]);
    }
    puts("");
  }
}

```