#include <bits/stdc++.h>
using namespace std;
int const N = 100100;
int n, an[N + 1];
void go0() {
  if (n & 1) {
    printf("NO\n");
    return;
  }
  for (int i = 1; i < (int)(n + 1); ++i) an[i] = 0;
  for (int i = n; i > 0; --i)
    if (an[i] == 0) {
      int t = ~i & (1 << 20) - 1;
      int j = 19;
      while (t > i) t ^= 1 << j, --j;
      an[i] = t;
      an[t] = i;
    }
  printf("YES\n");
  printf("%d", an[1]);
  for (int i = 2; i < (int)(n + 1); ++i) printf(" %d", an[i]);
  printf("\n");
}
int const M = 3000000;
int E, Pa[N], VIS[N], VS, SR, TR;
vector<int> G[N];
pair<int, int> Ed[M];
bool path(int v = SR) {
  if (v == TR) return true;
  VIS[v] = VS;
  for (int i = 0; i < (int)(G[v].size()); ++i) {
    pair<int, int> &e = Ed[G[v][i]];
    if (e.second == 0) continue;
    if (VIS[e.first] != VS && path(e.first)) {
      Pa[e.first] = G[v][i];
      return true;
    }
  }
  return false;
}
int fix() {
  int an = 2e9, v = TR;
  while (v != SR) {
    int e = Pa[v];
    an = min(an, Ed[e].second);
    v = Ed[e ^ 1].first;
  }
  v = TR;
  while (v != SR) {
    int e = Pa[v];
    Ed[e].second -= an;
    Ed[e ^ 1].second += an;
    v = Ed[e ^ 1].first;
  }
  return an;
}
inline int MF(int a, int b) {
  SR = a, TR = b;
  int an = 0;
  ++VS;
  while (path()) an += fix(), ++VS;
  return an;
}
inline void aded(int a, int b, int w1 = 1, int w2 = 0) {
  Ed[E] = make_pair(b, w1);
  Ed[E + 1] = make_pair(a, w2);
  G[a].push_back(E++);
  G[b].push_back(E++);
}
inline void CL() {
  E = 0;
  for (int i = 0; i < (int)(N); ++i) G[i].clear();
}
vector<int> v[20];
void go1() {
  int sr = 0, tr = n + 21;
  for (int i = 1; i < (int)(n + 1); ++i) aded(sr, i);
  for (int i = 1; i < (int)(n + 1); ++i)
    for (int j = 0; j < (int)(20); ++j)
      if (i >> j & 1) aded(i, n + j + 1);
  for (int i = 0; i < (int)(20); ++i) aded(n + i + 1, tr, 2);
  int mx = 19;
  while (n >> mx == 0) --mx;
  if (MF(sr, tr) != mx + 1 << 1) {
    printf("NO\n");
    return;
  }
  for (int i = 1; i < (int)(n + 1); ++i) {
    int e = G[i][0];
    if (!Ed[e].second) {
      int z = 0;
      while (!(i >> z & 1)) ++z;
      v[z].push_back(i);
    } else {
      int u;
      for (int j = 1; j < (int)(G[i].size()); ++j)
        if (Ed[G[i][j]].second == 0) {
          u = Ed[G[i][j]].first - n - 1;
          break;
        }
      v[u].push_back(i);
    }
  }
  for (int i = 1; i < (int)(n + 1); ++i) an[i] = i;
  for (int i = 0; i < (int)(mx + 1); ++i) {
    for (int j = v[i].size() - 1; j > 0; --j) an[v[i][j]] = an[v[i][j - 1]];
    an[v[i][0]] = v[i].back();
  }
  printf("YES\n");
  printf("%d", an[1]);
  for (int i = 2; i < (int)(n + 1); ++i) printf(" %d", an[i]);
  printf("\n");
}
int main() {
  scanf("%d", &n);
  go0();
  go1();
}

### Prompt

Please create a solution in cpp 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;
int const N = 100100;
int n, an[N + 1];
void go0() {
  if (n & 1) {
    printf("NO\n");
    return;
  }
  for (int i = 1; i < (int)(n + 1); ++i) an[i] = 0;
  for (int i = n; i > 0; --i)
    if (an[i] == 0) {
      int t = ~i & (1 << 20) - 1;
      int j = 19;
      while (t > i) t ^= 1 << j, --j;
      an[i] = t;
      an[t] = i;
    }
  printf("YES\n");
  printf("%d", an[1]);
  for (int i = 2; i < (int)(n + 1); ++i) printf(" %d", an[i]);
  printf("\n");
}
int const M = 3000000;
int E, Pa[N], VIS[N], VS, SR, TR;
vector<int> G[N];
pair<int, int> Ed[M];
bool path(int v = SR) {
  if (v == TR) return true;
  VIS[v] = VS;
  for (int i = 0; i < (int)(G[v].size()); ++i) {
    pair<int, int> &e = Ed[G[v][i]];
    if (e.second == 0) continue;
    if (VIS[e.first] != VS && path(e.first)) {
      Pa[e.first] = G[v][i];
      return true;
    }
  }
  return false;
}
int fix() {
  int an = 2e9, v = TR;
  while (v != SR) {
    int e = Pa[v];
    an = min(an, Ed[e].second);
    v = Ed[e ^ 1].first;
  }
  v = TR;
  while (v != SR) {
    int e = Pa[v];
    Ed[e].second -= an;
    Ed[e ^ 1].second += an;
    v = Ed[e ^ 1].first;
  }
  return an;
}
inline int MF(int a, int b) {
  SR = a, TR = b;
  int an = 0;
  ++VS;
  while (path()) an += fix(), ++VS;
  return an;
}
inline void aded(int a, int b, int w1 = 1, int w2 = 0) {
  Ed[E] = make_pair(b, w1);
  Ed[E + 1] = make_pair(a, w2);
  G[a].push_back(E++);
  G[b].push_back(E++);
}
inline void CL() {
  E = 0;
  for (int i = 0; i < (int)(N); ++i) G[i].clear();
}
vector<int> v[20];
void go1() {
  int sr = 0, tr = n + 21;
  for (int i = 1; i < (int)(n + 1); ++i) aded(sr, i);
  for (int i = 1; i < (int)(n + 1); ++i)
    for (int j = 0; j < (int)(20); ++j)
      if (i >> j & 1) aded(i, n + j + 1);
  for (int i = 0; i < (int)(20); ++i) aded(n + i + 1, tr, 2);
  int mx = 19;
  while (n >> mx == 0) --mx;
  if (MF(sr, tr) != mx + 1 << 1) {
    printf("NO\n");
    return;
  }
  for (int i = 1; i < (int)(n + 1); ++i) {
    int e = G[i][0];
    if (!Ed[e].second) {
      int z = 0;
      while (!(i >> z & 1)) ++z;
      v[z].push_back(i);
    } else {
      int u;
      for (int j = 1; j < (int)(G[i].size()); ++j)
        if (Ed[G[i][j]].second == 0) {
          u = Ed[G[i][j]].first - n - 1;
          break;
        }
      v[u].push_back(i);
    }
  }
  for (int i = 1; i < (int)(n + 1); ++i) an[i] = i;
  for (int i = 0; i < (int)(mx + 1); ++i) {
    for (int j = v[i].size() - 1; j > 0; --j) an[v[i][j]] = an[v[i][j - 1]];
    an[v[i][0]] = v[i].back();
  }
  printf("YES\n");
  printf("%d", an[1]);
  for (int i = 2; i < (int)(n + 1); ++i) printf(" %d", an[i]);
  printf("\n");
}
int main() {
  scanf("%d", &n);
  go0();
  go1();
}

```