#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int N = (int)1e5 + 7;
int lg[N];
vector<int> solveP(int n) {
  if (n == 0) return vector<int>();
  int offset = n - (1 << lg[n]);
  if (offset == 0) {
    auto res = solveP(n - 2);
    res.push_back(n);
    res.push_back(n - 1);
    return res;
  }
  auto res = solveP(n - offset);
  for (auto &it : res)
    if (it <= offset) it += n - offset;
  auto extra = solveP(offset);
  for (auto it : extra) res.push_back(it);
  return res;
}
vector<int> q[1010];
bool used[1011];
int mt[1010];
bool try_kuhn(int v) {
  if (used[v]) return false;
  used[v] = true;
  for (auto to : q[v]) {
    if (mt[to] == -1 || try_kuhn(mt[to])) {
      mt[to] = v;
      return true;
    }
  }
  return false;
}
vector<int> solveQ(int n) {
  if (n == 0) return vector<int>();
  if (n <= 100) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (i != j) {
          if ((i & j) != 0) q[i].push_back(j);
        }
      }
    }
    memset(mt, -1, sizeof mt);
    for (int v = 1; v <= n; v++) {
      memset(used, 0, sizeof used);
      try_kuhn(v);
    }
    vector<int> ans;
    for (int i = 1; i <= n; i++)
      if (mt[i] == -1) {
        cout << "NO";
        exit(0);
      } else
        ans.push_back(mt[i]);
    return ans;
  }
  if (n & 1) {
    auto res = solveQ(n - 2);
    res.push_back(n);
    res.push_back(n - 1);
    return res;
  }
  vector<int> odd;
  for (int i = 3; i <= n; i += 2) odd.push_back(i);
  odd.push_back(1);
  auto rec = solveQ(n / 2);
  vector<int> res(n);
  for (int i = 0, j = 0; i < n; i += 2, j++) {
    res[i] = odd[j];
  }
  for (int i = 1; i < n; i += 2) res[i] = rec[i / 2] * 2;
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  if (n & 1) {
    cout << "NO\n";
  } else {
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    vector<int> p = solveP(n);
    for (int i = 1; i <= n; i++)
      if (p[i - 1] == i || ((p[i - 1] & i) != 0)) assert(false);
    cout << "YES\n";
    for (auto it : p) cout << it << ' ';
    cout << '\n';
  }
  vector<int> q = solveQ(n);
  for (int i = 1; i <= n; i++)
    if (q[i - 1] == i || ((q[i - 1] & i) == 0)) {
      assert(false);
    }
  cout << "YES\n";
  for (auto it : q) cout << it << ' ';
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 MOD = (int)1e9 + 7;
const int N = (int)1e5 + 7;
int lg[N];
vector<int> solveP(int n) {
  if (n == 0) return vector<int>();
  int offset = n - (1 << lg[n]);
  if (offset == 0) {
    auto res = solveP(n - 2);
    res.push_back(n);
    res.push_back(n - 1);
    return res;
  }
  auto res = solveP(n - offset);
  for (auto &it : res)
    if (it <= offset) it += n - offset;
  auto extra = solveP(offset);
  for (auto it : extra) res.push_back(it);
  return res;
}
vector<int> q[1010];
bool used[1011];
int mt[1010];
bool try_kuhn(int v) {
  if (used[v]) return false;
  used[v] = true;
  for (auto to : q[v]) {
    if (mt[to] == -1 || try_kuhn(mt[to])) {
      mt[to] = v;
      return true;
    }
  }
  return false;
}
vector<int> solveQ(int n) {
  if (n == 0) return vector<int>();
  if (n <= 100) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (i != j) {
          if ((i & j) != 0) q[i].push_back(j);
        }
      }
    }
    memset(mt, -1, sizeof mt);
    for (int v = 1; v <= n; v++) {
      memset(used, 0, sizeof used);
      try_kuhn(v);
    }
    vector<int> ans;
    for (int i = 1; i <= n; i++)
      if (mt[i] == -1) {
        cout << "NO";
        exit(0);
      } else
        ans.push_back(mt[i]);
    return ans;
  }
  if (n & 1) {
    auto res = solveQ(n - 2);
    res.push_back(n);
    res.push_back(n - 1);
    return res;
  }
  vector<int> odd;
  for (int i = 3; i <= n; i += 2) odd.push_back(i);
  odd.push_back(1);
  auto rec = solveQ(n / 2);
  vector<int> res(n);
  for (int i = 0, j = 0; i < n; i += 2, j++) {
    res[i] = odd[j];
  }
  for (int i = 1; i < n; i += 2) res[i] = rec[i / 2] * 2;
  return res;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  if (n & 1) {
    cout << "NO\n";
  } else {
    for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
    vector<int> p = solveP(n);
    for (int i = 1; i <= n; i++)
      if (p[i - 1] == i || ((p[i - 1] & i) != 0)) assert(false);
    cout << "YES\n";
    for (auto it : p) cout << it << ' ';
    cout << '\n';
  }
  vector<int> q = solveQ(n);
  for (int i = 1; i <= n; i++)
    if (q[i - 1] == i || ((q[i - 1] & i) == 0)) {
      assert(false);
    }
  cout << "YES\n";
  for (auto it : q) cout << it << ' ';
  return 0;
}

```