#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
int a[MAXN];
void solve1(int n) {
  int rem = n;
  while (rem > 0) {
    int bit = 0;
    while ((2 << bit) <= rem) ++bit;
    int want = (2 << bit) - 1;
    int orem = rem;
    while (want - (rem - 1) <= orem) a[rem - 1] = want - (rem - 1), --rem;
  }
}
int ans1[MAXN];
int ans2[MAXN];
bool solve2(int n) {
  if (n < 6) return false;
  ans2[0] = 3, ans2[1] = 6, ans2[2] = 2, ans2[3] = 5, ans2[4] = 1, ans2[5] = 4;
  int pos = 5;
  bool skipped = false;
  for (int i = (6); i < (n); ++i) {
    int val = i + 1;
    if ((val & (val - 1)) == 0) {
      skipped = true;
      continue;
    }
    if (skipped) {
      skipped = false;
      ans2[i - 1] = val;
      ans2[i] = val - 1;
      pos = i;
      continue;
    }
    ans2[i] = ans2[pos];
    ans2[pos] = val;
    pos = i;
  }
  return !skipped;
}
void run() {
  int n;
  scanf("%d", &n);
  if (n % 2 == 1) {
    printf("NO\n");
  } else {
    solve1(n / 2);
    for (int i = (0); i < (n / 2); ++i)
      ans1[2 * i] = 2 * a[i], ans1[2 * a[i] - 1] = 2 * i + 1;
    printf("YES\n");
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", ans1[i]);
    }
    puts("");
  }
  if (!solve2(n)) {
    printf("NO\n");
  } else {
    printf("YES\n");
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", ans2[i]);
    }
    puts("");
  }
}
int main() {
  run();
  return 0;
}

### Prompt

In Cpp, your task is to solve 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;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 100000;
int a[MAXN];
void solve1(int n) {
  int rem = n;
  while (rem > 0) {
    int bit = 0;
    while ((2 << bit) <= rem) ++bit;
    int want = (2 << bit) - 1;
    int orem = rem;
    while (want - (rem - 1) <= orem) a[rem - 1] = want - (rem - 1), --rem;
  }
}
int ans1[MAXN];
int ans2[MAXN];
bool solve2(int n) {
  if (n < 6) return false;
  ans2[0] = 3, ans2[1] = 6, ans2[2] = 2, ans2[3] = 5, ans2[4] = 1, ans2[5] = 4;
  int pos = 5;
  bool skipped = false;
  for (int i = (6); i < (n); ++i) {
    int val = i + 1;
    if ((val & (val - 1)) == 0) {
      skipped = true;
      continue;
    }
    if (skipped) {
      skipped = false;
      ans2[i - 1] = val;
      ans2[i] = val - 1;
      pos = i;
      continue;
    }
    ans2[i] = ans2[pos];
    ans2[pos] = val;
    pos = i;
  }
  return !skipped;
}
void run() {
  int n;
  scanf("%d", &n);
  if (n % 2 == 1) {
    printf("NO\n");
  } else {
    solve1(n / 2);
    for (int i = (0); i < (n / 2); ++i)
      ans1[2 * i] = 2 * a[i], ans1[2 * a[i] - 1] = 2 * i + 1;
    printf("YES\n");
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", ans1[i]);
    }
    puts("");
  }
  if (!solve2(n)) {
    printf("NO\n");
  } else {
    printf("YES\n");
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", ans2[i]);
    }
    puts("");
  }
}
int main() {
  run();
  return 0;
}

```