#include <bits/stdc++.h>
using namespace std;
static inline void fastkek() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}
void do_zero(int n) {
  static int p[100000 + 2];
  int k;
  if (n % 2) {
    puts("NO");
    return;
  }
  puts("YES");
  k = n;
  while (k) {
    int b = 1 << (31 ^ __builtin_clz(k));
    int l = k - b;
    for (int i = 0; i <= l; ++i) {
      int x = b - 1 - i, y = b + i;
      p[x] = y;
      p[y] = x;
    }
    k = 2 * b - k - 2;
  }
  for (int i = 1; i <= n; ++i) printf("%d ", p[i]);
  putchar('\n');
}
void do_nz(int n) {
  static int q[100000 + 2] = {0, 5, 3, 6, 7, 4, 2, 1};
  int l = 8, h;
  if (n < 6 || !(n & (n - 1))) {
    puts("NO");
    return;
  }
  puts("YES");
  if (n == 6) {
    puts("3 6 1 5 4 2");
    return;
  }
  while (l < n) {
    h = min(2 * l - 1, n);
    for (int i = l; i < h; ++i) q[i] = i + 1;
    q[h] = l;
    l *= 2;
  }
  for (int i = 1; i <= n; ++i) printf("%d ", q[i]);
  putchar('\n');
}
int main() {
  int n;
  scanf("%d", &n);
  do_zero(n);
  do_nz(n);
  return 0;
}

### Prompt

Please formulate a cpp solution 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;
static inline void fastkek() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}
void do_zero(int n) {
  static int p[100000 + 2];
  int k;
  if (n % 2) {
    puts("NO");
    return;
  }
  puts("YES");
  k = n;
  while (k) {
    int b = 1 << (31 ^ __builtin_clz(k));
    int l = k - b;
    for (int i = 0; i <= l; ++i) {
      int x = b - 1 - i, y = b + i;
      p[x] = y;
      p[y] = x;
    }
    k = 2 * b - k - 2;
  }
  for (int i = 1; i <= n; ++i) printf("%d ", p[i]);
  putchar('\n');
}
void do_nz(int n) {
  static int q[100000 + 2] = {0, 5, 3, 6, 7, 4, 2, 1};
  int l = 8, h;
  if (n < 6 || !(n & (n - 1))) {
    puts("NO");
    return;
  }
  puts("YES");
  if (n == 6) {
    puts("3 6 1 5 4 2");
    return;
  }
  while (l < n) {
    h = min(2 * l - 1, n);
    for (int i = l; i < h; ++i) q[i] = i + 1;
    q[h] = l;
    l *= 2;
  }
  for (int i = 1; i <= n; ++i) printf("%d ", q[i]);
  putchar('\n');
}
int main() {
  int n;
  scanf("%d", &n);
  do_zero(n);
  do_nz(n);
  return 0;
}

```