#include <bits/stdc++.h>
using namespace std;
void readln(int& I) {
  I = 0;
  char C = getchar();
  while (!isdigit(C)) C = getchar();
  while (isdigit(C)) I = I * 10 + C - '0', C = getchar();
}
int n, p[100005];
int cb(int x) {
  int res = 0;
  while (x) res += (x & 1), x >>= 1;
  return res;
}
inline void f1(int x) {
  if (!x) return;
  int u = 1;
  while (2 * u <= x) u <<= 1;
  for (register int i = ((u << 1) - 1 - x); i <= x; i++)
    p[i] = x + ((u << 1) - 1 - x) - i;
  f1(((u << 1) - 1 - x) - 1);
}
inline void f2(int x) {
  int k = 0;
  for (k = 0; (1 << (k + 1)) - 1 <= x; k++) {
    for (register int j = (1 << k) + 1; j < (1 << (k + 1)); j++) p[j] = j - 1;
    p[1 << k] = (1 << (k + 1)) - 1;
  }
  if ((1 << k) - 1 <= x) {
    for (register int j = (1 << k) + 1; j <= n; j++) p[j] = j - 1;
    p[1 << k] = n;
  }
  const int dirr[] = {0, 7, 3, 2, 5, 6, 4, 1, -1};
  for (register int i = 1; dirr[i] > 0; i++) p[i] = dirr[i];
}
inline void op() {
  puts("YES");
  for (register int i = 1; i <= n; i++) printf("%d ", p[i]);
  putchar(10);
}
int main() {
  readln(n);
  if (n & 1)
    puts("NO");
  else
    f1(n), op();
  if (n == 6) return puts("YES\n3 6 1 5 4 2"), 0;
  if (cb(n) == 1 || n <= 5)
    puts("NO");
  else
    f2(n), op();
}

### Prompt

Develop a solution in CPP to the problem described below:

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;
void readln(int& I) {
  I = 0;
  char C = getchar();
  while (!isdigit(C)) C = getchar();
  while (isdigit(C)) I = I * 10 + C - '0', C = getchar();
}
int n, p[100005];
int cb(int x) {
  int res = 0;
  while (x) res += (x & 1), x >>= 1;
  return res;
}
inline void f1(int x) {
  if (!x) return;
  int u = 1;
  while (2 * u <= x) u <<= 1;
  for (register int i = ((u << 1) - 1 - x); i <= x; i++)
    p[i] = x + ((u << 1) - 1 - x) - i;
  f1(((u << 1) - 1 - x) - 1);
}
inline void f2(int x) {
  int k = 0;
  for (k = 0; (1 << (k + 1)) - 1 <= x; k++) {
    for (register int j = (1 << k) + 1; j < (1 << (k + 1)); j++) p[j] = j - 1;
    p[1 << k] = (1 << (k + 1)) - 1;
  }
  if ((1 << k) - 1 <= x) {
    for (register int j = (1 << k) + 1; j <= n; j++) p[j] = j - 1;
    p[1 << k] = n;
  }
  const int dirr[] = {0, 7, 3, 2, 5, 6, 4, 1, -1};
  for (register int i = 1; dirr[i] > 0; i++) p[i] = dirr[i];
}
inline void op() {
  puts("YES");
  for (register int i = 1; i <= n; i++) printf("%d ", p[i]);
  putchar(10);
}
int main() {
  readln(n);
  if (n & 1)
    puts("NO");
  else
    f1(n), op();
  if (n == 6) return puts("YES\n3 6 1 5 4 2"), 0;
  if (cb(n) == 1 || n <= 5)
    puts("NO");
  else
    f2(n), op();
}

```