#include <bits/stdc++.h>
using namespace std;
const int block_size = 320;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 7;
const long double eps = 1e-9;
const double PI = atan(1) * 4;
template <typename T>
inline int sign(const T &a) {
  if (a < 0) return -1;
  if (a > 0) return 1;
  return 0;
}
template <typename T>
inline void in(T &x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
long long twop(int x) { return 1LL << x; }
template <typename A, typename B>
inline void in(A &x, B &y) {
  in(x);
  in(y);
}
template <typename A, typename B, typename C>
inline void in(A &x, B &y, C &z) {
  in(x);
  in(y);
  in(z);
}
template <typename A, typename B, typename C, typename D>
inline void in(A &x, B &y, C &z, D &d) {
  in(x);
  in(y);
  in(z);
  in(d);
}
template <class T>
void upd(T &a, T b) {
  a = max(a, b);
}
int n;
int perm[(1 << 17) + 1];
void print() {
  cout << "YES\n";
  for (long long i = 1; i < n + 1; i++) {
    cout << perm[i] << " ";
  }
  cout << endl;
}
void sa() {
  if (n % 2 == 1) {
    cout << "NO\n";
    return;
  }
  for (int i = 17; i >= 0; i--) {
    for (int j = 1; twop(i) + j - 1 <= n; j++) {
      if (perm[twop(i) + j - 1]) break;
      perm[twop(i) + j - 1] = twop(i) - j;
      perm[twop(i) - j] = twop(i) + j - 1;
    }
  }
  print();
}
int highBit(int x) {
  for (long long i = 20; i >= 0; i--) {
    if (twop(i) & x) return i;
  }
  return -1;
}
bool check(int n) {
  for (long long i = 1; i < n + 1; i++) {
    if (perm[i] == i || (perm[i] & i) == 0) return false;
  }
  return true;
}
void sb() {
  int nn = n;
  if ((n & (-n)) == n) {
    cout << "NO\n";
    return;
  }
  while (nn > 7) {
    vector<int> tmp;
    while (nn > 7 && ((int)tmp.size()) == 0 ||
           highBit(nn) == highBit(tmp.back())) {
      tmp.push_back(nn--);
    }
    tmp.push_back(tmp[0]);
    for (long long i = 0; i < ((int)tmp.size()) - 1; i++)
      perm[tmp[i]] = tmp[i + 1];
  }
  for (long long i = 1; i < nn + 1; i++) perm[i] = i;
  bool ok = 0;
  do {
    if (check(nn)) {
      ok = 1;
      break;
    };
  } while (next_permutation(perm + 1, perm + 1 + nn));
  if (!ok) {
    cout << "NO\n";
    return;
  }
  print();
}
int main() {
  cin >> n;
  sa();
  sb();
  return 0;
}

### Prompt

Generate 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 block_size = 320;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 7;
const long double eps = 1e-9;
const double PI = atan(1) * 4;
template <typename T>
inline int sign(const T &a) {
  if (a < 0) return -1;
  if (a > 0) return 1;
  return 0;
}
template <typename T>
inline void in(T &x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
long long twop(int x) { return 1LL << x; }
template <typename A, typename B>
inline void in(A &x, B &y) {
  in(x);
  in(y);
}
template <typename A, typename B, typename C>
inline void in(A &x, B &y, C &z) {
  in(x);
  in(y);
  in(z);
}
template <typename A, typename B, typename C, typename D>
inline void in(A &x, B &y, C &z, D &d) {
  in(x);
  in(y);
  in(z);
  in(d);
}
template <class T>
void upd(T &a, T b) {
  a = max(a, b);
}
int n;
int perm[(1 << 17) + 1];
void print() {
  cout << "YES\n";
  for (long long i = 1; i < n + 1; i++) {
    cout << perm[i] << " ";
  }
  cout << endl;
}
void sa() {
  if (n % 2 == 1) {
    cout << "NO\n";
    return;
  }
  for (int i = 17; i >= 0; i--) {
    for (int j = 1; twop(i) + j - 1 <= n; j++) {
      if (perm[twop(i) + j - 1]) break;
      perm[twop(i) + j - 1] = twop(i) - j;
      perm[twop(i) - j] = twop(i) + j - 1;
    }
  }
  print();
}
int highBit(int x) {
  for (long long i = 20; i >= 0; i--) {
    if (twop(i) & x) return i;
  }
  return -1;
}
bool check(int n) {
  for (long long i = 1; i < n + 1; i++) {
    if (perm[i] == i || (perm[i] & i) == 0) return false;
  }
  return true;
}
void sb() {
  int nn = n;
  if ((n & (-n)) == n) {
    cout << "NO\n";
    return;
  }
  while (nn > 7) {
    vector<int> tmp;
    while (nn > 7 && ((int)tmp.size()) == 0 ||
           highBit(nn) == highBit(tmp.back())) {
      tmp.push_back(nn--);
    }
    tmp.push_back(tmp[0]);
    for (long long i = 0; i < ((int)tmp.size()) - 1; i++)
      perm[tmp[i]] = tmp[i + 1];
  }
  for (long long i = 1; i < nn + 1; i++) perm[i] = i;
  bool ok = 0;
  do {
    if (check(nn)) {
      ok = 1;
      break;
    };
  } while (next_permutation(perm + 1, perm + 1 + nn));
  if (!ok) {
    cout << "NO\n";
    return;
  }
  print();
}
int main() {
  cin >> n;
  sa();
  sb();
  return 0;
}

```