#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 3;
const int infint = (int)2e9;
const long long inf = (long long)2e18;
int n;
vector<int> getans(int l1, int r1, int l2, int r2) {
  if (r1 == l1) {
    vector<int> v;
    v.push_back(l2);
    return v;
  }
  if (l1 == 0 && l2 == 0 && r1 % 2 == 0) {
    vector<int> ans = getans(l1 + 1, r1, l2 + 1, r2);
    vector<int> p;
    p.push_back(0);
    for (auto u : ans) p.push_back(u);
    return p;
  }
  if (l1 % 2 != l2 % 2) {
    vector<int> c1 =
        getans(l1 / 2, l1 / 2 + (r1 - l1) / 2, l2 / 2, l2 / 2 + (r2 - l2) / 2);
    vector<int> c2 = getans((l1 + 1) / 2, (l1 + 1) / 2 + (r1 - l1 - 1) / 2,
                            (l2 + 1) / 2, (l2 + 1) / 2 + (r2 - l2 - 1) / 2);
    vector<int> ans(r1 - l1 + 1);
    for (int i = 0; i < r1 - l1 + 1; i++)
      if (i % 2 == 0)
        ans[i] = l2 + 2 * (c1[i / 2] - l2 / 2);
      else
        ans[i] = l2 + 1 + 2 * (c2[i / 2] - (l2 + 1) / 2);
    return ans;
  } else {
    vector<int> c1 = getans(l1 / 2, l1 / 2 + (r1 - l1) / 2, (l2 + 1) / 2,
                            (l2 + 1) / 2 + (r2 - l2 - 1) / 2);
    vector<int> c2 = getans((l1 + 1) / 2, (l1 + 1) / 2 + (r1 - l1 - 1) / 2,
                            l2 / 2, l2 / 2 + (r2 - l2) / 2);
    vector<int> ans(r1 - l1 + 1);
    for (int i = 0; i < r1 - l1 + 1; i++)
      if (i % 2 == 0)
        ans[i] = l2 + 1 + 2 * (c1[i / 2] - (l2 + 1) / 2);
      else
        ans[i] = l2 + 2 * (c2[i / 2] - l2 / 2);
    return ans;
  }
}
int pwr2(int n) {
  int c = n;
  while ((c & 1) == 0) c >>= 1;
  if (c == 1) return 1;
  return 0;
}
vector<int> per;
void solve(int n) {
  if (n == 6) {
    per.push_back(3);
    per.push_back(6);
    per.push_back(1);
    per.push_back(5);
    per.push_back(4);
    per.push_back(2);
    return;
  }
  if (n == 7) {
    per.push_back(7);
    per.push_back(3);
    per.push_back(6);
    per.push_back(5);
    per.push_back(1);
    per.push_back(4);
    per.push_back(2);
    return;
  }
  if (!pwr2(n - 2)) {
    solve(n - 2);
    per.push_back(n);
    per.push_back(n - 1);
    return;
  } else {
    solve(n - 4);
    per.push_back(n);
    per.push_back(n - 1);
    per.push_back(n - 2);
    per.push_back(n - 3);
    return;
  }
}
bool check(vector<int> v) {
  for (int i = 0; i < v.size(); i++)
    if (i + 1 == v[i] || ((i + 1) & v[i]) == 0) return 0;
  return 1;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  if (n % 2)
    cout << "NO\n";
  else {
    cout << "YES\n";
    vector<int> v = getans(0, n / 2 - 1, 1, n / 2);
    vector<int> rev(n / 2 + 1);
    for (int i = 0; i < v.size(); i++) rev[v[i]] = i;
    vector<int> ans;
    for (int i = 0; i < n; i++)
      if (i & 1)
        ans.push_back(rev[(i + 1) / 2] * 2 + 1);
      else
        ans.push_back(v[i >> 1] * 2);
    for (auto u : ans) cout << u << " ";
    cout << "\n";
  }
  if (n <= 5 || pwr2(n)) return cout << "NO", 0;
  cout << "YES\n";
  solve(n);
  for (auto u : per) cout << u << " ";
}

### 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;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 3;
const int infint = (int)2e9;
const long long inf = (long long)2e18;
int n;
vector<int> getans(int l1, int r1, int l2, int r2) {
  if (r1 == l1) {
    vector<int> v;
    v.push_back(l2);
    return v;
  }
  if (l1 == 0 && l2 == 0 && r1 % 2 == 0) {
    vector<int> ans = getans(l1 + 1, r1, l2 + 1, r2);
    vector<int> p;
    p.push_back(0);
    for (auto u : ans) p.push_back(u);
    return p;
  }
  if (l1 % 2 != l2 % 2) {
    vector<int> c1 =
        getans(l1 / 2, l1 / 2 + (r1 - l1) / 2, l2 / 2, l2 / 2 + (r2 - l2) / 2);
    vector<int> c2 = getans((l1 + 1) / 2, (l1 + 1) / 2 + (r1 - l1 - 1) / 2,
                            (l2 + 1) / 2, (l2 + 1) / 2 + (r2 - l2 - 1) / 2);
    vector<int> ans(r1 - l1 + 1);
    for (int i = 0; i < r1 - l1 + 1; i++)
      if (i % 2 == 0)
        ans[i] = l2 + 2 * (c1[i / 2] - l2 / 2);
      else
        ans[i] = l2 + 1 + 2 * (c2[i / 2] - (l2 + 1) / 2);
    return ans;
  } else {
    vector<int> c1 = getans(l1 / 2, l1 / 2 + (r1 - l1) / 2, (l2 + 1) / 2,
                            (l2 + 1) / 2 + (r2 - l2 - 1) / 2);
    vector<int> c2 = getans((l1 + 1) / 2, (l1 + 1) / 2 + (r1 - l1 - 1) / 2,
                            l2 / 2, l2 / 2 + (r2 - l2) / 2);
    vector<int> ans(r1 - l1 + 1);
    for (int i = 0; i < r1 - l1 + 1; i++)
      if (i % 2 == 0)
        ans[i] = l2 + 1 + 2 * (c1[i / 2] - (l2 + 1) / 2);
      else
        ans[i] = l2 + 2 * (c2[i / 2] - l2 / 2);
    return ans;
  }
}
int pwr2(int n) {
  int c = n;
  while ((c & 1) == 0) c >>= 1;
  if (c == 1) return 1;
  return 0;
}
vector<int> per;
void solve(int n) {
  if (n == 6) {
    per.push_back(3);
    per.push_back(6);
    per.push_back(1);
    per.push_back(5);
    per.push_back(4);
    per.push_back(2);
    return;
  }
  if (n == 7) {
    per.push_back(7);
    per.push_back(3);
    per.push_back(6);
    per.push_back(5);
    per.push_back(1);
    per.push_back(4);
    per.push_back(2);
    return;
  }
  if (!pwr2(n - 2)) {
    solve(n - 2);
    per.push_back(n);
    per.push_back(n - 1);
    return;
  } else {
    solve(n - 4);
    per.push_back(n);
    per.push_back(n - 1);
    per.push_back(n - 2);
    per.push_back(n - 3);
    return;
  }
}
bool check(vector<int> v) {
  for (int i = 0; i < v.size(); i++)
    if (i + 1 == v[i] || ((i + 1) & v[i]) == 0) return 0;
  return 1;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  if (n % 2)
    cout << "NO\n";
  else {
    cout << "YES\n";
    vector<int> v = getans(0, n / 2 - 1, 1, n / 2);
    vector<int> rev(n / 2 + 1);
    for (int i = 0; i < v.size(); i++) rev[v[i]] = i;
    vector<int> ans;
    for (int i = 0; i < n; i++)
      if (i & 1)
        ans.push_back(rev[(i + 1) / 2] * 2 + 1);
      else
        ans.push_back(v[i >> 1] * 2);
    for (auto u : ans) cout << u << " ";
    cout << "\n";
  }
  if (n <= 5 || pwr2(n)) return cout << "NO", 0;
  cout << "YES\n";
  solve(n);
  for (auto u : per) cout << u << " ";
}

```