#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 51;
int n, x;
int res[MAXN];
inline int read() {
  register int num = 0, neg = 1;
  register char ch = getchar();
  while (!isdigit(ch) && ch != '-') {
    ch = getchar();
  }
  if (ch == '-') {
    neg = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    num = (num << 3) + (num << 1) + (ch - '0');
    ch = getchar();
  }
  return num * neg;
}
inline void calc1(int n) {
  if (n <= 0) {
    return;
  }
  int x = 31 - __builtin_clz(n);
  reverse(res + (1 << x + 1) - n - 1, res + n + 1);
  calc1((1 << x + 1) - n - 2);
}
inline void solve1() {
  if (n & 1) {
    return (void)puts("NO");
  }
  puts("YES");
  for (register int i = 1; i <= n; i++) {
    res[i] = i;
  }
  calc1(n);
  for (register int i = 1; i <= n; i++) {
    printf("%d ", res[i]);
  }
  puts("");
}
inline void solve2() {
  if (n == 3 || n == 5 || n == (n & -n)) {
    return (void)puts("NO");
  }
  puts("YES");
  for (register int i = 1; i <= n; i++) {
    res[i] = i;
  }
  if (n & 1) {
    printf("3 6 1 5 7 2 4 ");
    for (register int i = 8; i <= n; i += 2) {
      swap(res[i], res[i ^ 1]);
    }
    for (register int i = 8; i <= n; i++) {
      printf("%d ", res[i]);
    }
  } else {
    for (register int i = 2; i <= n - 3; i += 2) {
      swap(res[i], res[i + 1]);
    }
    swap(res[1], res[n - 1]), swap(res[n], res[n - 2]);
    for (register int i = 1; i <= n; i++) {
      printf("%d ", res[i]);
    }
  }
  puts("");
}
int main() { n = read(), solve1(), solve2(); }

### Prompt

Your task is to create 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;
const int MAXN = 2e5 + 51;
int n, x;
int res[MAXN];
inline int read() {
  register int num = 0, neg = 1;
  register char ch = getchar();
  while (!isdigit(ch) && ch != '-') {
    ch = getchar();
  }
  if (ch == '-') {
    neg = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    num = (num << 3) + (num << 1) + (ch - '0');
    ch = getchar();
  }
  return num * neg;
}
inline void calc1(int n) {
  if (n <= 0) {
    return;
  }
  int x = 31 - __builtin_clz(n);
  reverse(res + (1 << x + 1) - n - 1, res + n + 1);
  calc1((1 << x + 1) - n - 2);
}
inline void solve1() {
  if (n & 1) {
    return (void)puts("NO");
  }
  puts("YES");
  for (register int i = 1; i <= n; i++) {
    res[i] = i;
  }
  calc1(n);
  for (register int i = 1; i <= n; i++) {
    printf("%d ", res[i]);
  }
  puts("");
}
inline void solve2() {
  if (n == 3 || n == 5 || n == (n & -n)) {
    return (void)puts("NO");
  }
  puts("YES");
  for (register int i = 1; i <= n; i++) {
    res[i] = i;
  }
  if (n & 1) {
    printf("3 6 1 5 7 2 4 ");
    for (register int i = 8; i <= n; i += 2) {
      swap(res[i], res[i ^ 1]);
    }
    for (register int i = 8; i <= n; i++) {
      printf("%d ", res[i]);
    }
  } else {
    for (register int i = 2; i <= n - 3; i += 2) {
      swap(res[i], res[i + 1]);
    }
    swap(res[1], res[n - 1]), swap(res[n], res[n - 2]);
    for (register int i = 1; i <= n; i++) {
      printf("%d ", res[i]);
    }
  }
  puts("");
}
int main() { n = read(), solve1(), solve2(); }

```