#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
void __dump(int x) { cerr << x; }
void __dump(long long x) { cerr << x; }
void __dump(long double x) { cerr << fixed << setprecision(3) << x; }
void __dump(char x) { cerr << '\'' << x << '\''; }
void __dump(const string &x) { cerr << '"' << x << '"'; }
void __dump(const char *x) { cerr << '"' << x << '"'; }
void __dump(bool x) { cerr << (x ? "true" : "false"); }
void _dump() { cerr << "\n"; }
template <typename T, typename U>
void __dump(const pair<T, U> &x) {
  cerr << '{';
  __dump(x.first);
  cerr << ',';
  __dump(x.second);
  cerr << '}';
}
template <typename T, typename U, typename V>
void __dump(const tuple<T, U, V> &x) {
  cerr << '{';
  __dump(get<0>(x));
  cerr << ',';
  __dump(get<1>(x));
  cerr << ',';
  __dump(get<2>(x));
  cerr << '}';
}
template <typename T>
void __dump(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __dump(i);
  cerr << "}";
}
template <typename T, typename... U>
void _dump(T t, U... u) {
  __dump(t);
  if (sizeof...(u)) cerr << ", ";
  _dump(u...);
}
const int INF = 1e9;
const int N = 2e5;
int n;
int mx_bit;
int perm1[N + 2], perm2[N + 2];
bool possible_permutation_1() {
  if (n % 2 == 1) return false;
  set<int> s;
  for (int i = 1; i <= n; ++i) {
    s.insert(i);
  }
  for (int i = n; i >= 1; --i) {
    if (!s.count(i)) continue;
    s.erase(i);
    int j = (1 << (31 - __builtin_clz(i) + 1)) - 1 - i;
    assert(s.count(j));
    s.erase(j);
    perm1[i] = j;
    perm1[j] = i;
  }
  return true;
}
bool possible_permutation_2() {
  if (n <= 5)
    return false;
  else if (n == (1 << mx_bit))
    return false;
  else if (n == 6) {
    perm2[1] = 3;
    perm2[2] = 6;
    perm2[3] = 2;
    perm2[4] = 5;
    perm2[5] = 1;
    perm2[6] = 4;
    return true;
  } else {
    for (int b = 1; b <= mx_bit; ++b) {
      vector<int> vect;
      for (int i = 1 << b; i <= min(n, (1 << (b + 1)) - 1); ++i) {
        vect.emplace_back(i);
      }
      assert((int)vect.size() >= 2);
      for (int ind = 1; ind <= (int)vect.size() - 1; ++ind) {
        int x = vect[ind];
        int y = vect[ind - 1];
        perm2[y] = x;
      }
      perm2[vect.back()] = vect.front();
    }
    assert(perm2[5] == 6);
    assert(perm2[6] == 7);
    assert(perm2[7] == 4);
    perm2[5] = 1;
    perm2[1] = 7;
    perm2[7] = 6;
    perm2[6] = 4;
    return true;
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  mx_bit = 31 - __builtin_clz(n);
  if (!possible_permutation_1())
    cout << "NO" << '\n';
  else {
    cout << "YES" << '\n';
    for (int i = 1; i <= n; ++i) {
      cout << perm1[i] << ' ';
    }
    cout << '\n';
  }
  if (!possible_permutation_2())
    cout << "NO" << '\n';
  else {
    cout << "YES" << '\n';
    for (int i = 1; i <= n; ++i) {
      cout << perm2[i] << ' ';
    }
    cout << '\n';
  }
}

### 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;
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
void __dump(int x) { cerr << x; }
void __dump(long long x) { cerr << x; }
void __dump(long double x) { cerr << fixed << setprecision(3) << x; }
void __dump(char x) { cerr << '\'' << x << '\''; }
void __dump(const string &x) { cerr << '"' << x << '"'; }
void __dump(const char *x) { cerr << '"' << x << '"'; }
void __dump(bool x) { cerr << (x ? "true" : "false"); }
void _dump() { cerr << "\n"; }
template <typename T, typename U>
void __dump(const pair<T, U> &x) {
  cerr << '{';
  __dump(x.first);
  cerr << ',';
  __dump(x.second);
  cerr << '}';
}
template <typename T, typename U, typename V>
void __dump(const tuple<T, U, V> &x) {
  cerr << '{';
  __dump(get<0>(x));
  cerr << ',';
  __dump(get<1>(x));
  cerr << ',';
  __dump(get<2>(x));
  cerr << '}';
}
template <typename T>
void __dump(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __dump(i);
  cerr << "}";
}
template <typename T, typename... U>
void _dump(T t, U... u) {
  __dump(t);
  if (sizeof...(u)) cerr << ", ";
  _dump(u...);
}
const int INF = 1e9;
const int N = 2e5;
int n;
int mx_bit;
int perm1[N + 2], perm2[N + 2];
bool possible_permutation_1() {
  if (n % 2 == 1) return false;
  set<int> s;
  for (int i = 1; i <= n; ++i) {
    s.insert(i);
  }
  for (int i = n; i >= 1; --i) {
    if (!s.count(i)) continue;
    s.erase(i);
    int j = (1 << (31 - __builtin_clz(i) + 1)) - 1 - i;
    assert(s.count(j));
    s.erase(j);
    perm1[i] = j;
    perm1[j] = i;
  }
  return true;
}
bool possible_permutation_2() {
  if (n <= 5)
    return false;
  else if (n == (1 << mx_bit))
    return false;
  else if (n == 6) {
    perm2[1] = 3;
    perm2[2] = 6;
    perm2[3] = 2;
    perm2[4] = 5;
    perm2[5] = 1;
    perm2[6] = 4;
    return true;
  } else {
    for (int b = 1; b <= mx_bit; ++b) {
      vector<int> vect;
      for (int i = 1 << b; i <= min(n, (1 << (b + 1)) - 1); ++i) {
        vect.emplace_back(i);
      }
      assert((int)vect.size() >= 2);
      for (int ind = 1; ind <= (int)vect.size() - 1; ++ind) {
        int x = vect[ind];
        int y = vect[ind - 1];
        perm2[y] = x;
      }
      perm2[vect.back()] = vect.front();
    }
    assert(perm2[5] == 6);
    assert(perm2[6] == 7);
    assert(perm2[7] == 4);
    perm2[5] = 1;
    perm2[1] = 7;
    perm2[7] = 6;
    perm2[6] = 4;
    return true;
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  mx_bit = 31 - __builtin_clz(n);
  if (!possible_permutation_1())
    cout << "NO" << '\n';
  else {
    cout << "YES" << '\n';
    for (int i = 1; i <= n; ++i) {
      cout << perm1[i] << ' ';
    }
    cout << '\n';
  }
  if (!possible_permutation_2())
    cout << "NO" << '\n';
  else {
    cout << "YES" << '\n';
    for (int i = 1; i <= n; ++i) {
      cout << perm2[i] << ' ';
    }
    cout << '\n';
  }
}

```