#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
  register int c = getchar();
  x = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
  if (neg) x = -x;
}
inline void writeln(int x) {
  char buffor[21];
  register int i = 0;
  int neg = 0;
  if (x < 0) {
    neg = 1;
    x = -x;
  }
  do {
    buffor[i++] = (x % 10) + '0';
    x /= 10;
  } while (x);
  i--;
  if (neg) putchar('-');
  while (i >= 0) putchar(buffor[i--]);
  putchar('\n');
}
int N, p[100010];
void input() { cin >> N; }
void solve1(int n) {
  if (n % 2 == 1) {
    cout << "NO" << '\n';
    return;
  }
  int s = 1;
  while (s * 2 <= n) s *= 2;
  while (n) {
    int l = s - 1;
    for (int r = s; r <= n; r++) {
      p[l] = r;
      p[r] = l;
      l--;
    }
    n = l;
    while (s > n) s /= 2;
  }
  cout << "YES" << '\n';
  for (int i = 1; i <= N; i++) cout << p[i] << " ";
  cout << '\n';
}
void solve2(int n) {
  if (n % 2 == 1 and n <= 5) {
    cout << "NO" << '\n';
    return;
  }
  if (n == 6) {
    cout << "YES" << '\n';
    cout << 3 << " " << 6 << " " << 1 << " " << 5 << " " << 4 << " " << 2;
    return;
  }
  int s = 1;
  while (s * 2 <= n) s *= 2;
  if (s == n) {
    cout << "NO" << '\n';
    return;
  }
  while (n >= 8) {
    for (int i = n; i >= s + 1; i--) p[i] = i - 1;
    p[s] = n;
    n = s - 1;
    s /= 2;
  }
  p[1] = 7;
  p[2] = 3;
  p[3] = 6;
  p[4] = 5;
  p[5] = 1;
  p[6] = 2;
  p[7] = 4;
  cout << "YES" << '\n';
  for (int i = 1; i <= N; i++) cout << p[i] << " ";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve1(N);
  solve2(N);
  return 0;
}

### Prompt

Create a solution in CPP for 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;
inline void read(int &x) {
  register int c = getchar();
  x = 0;
  int neg = 0;
  for (; ((c < 48 || c > 57) && c != '-'); c = getchar())
    ;
  if (c == '-') {
    neg = 1;
    c = getchar();
  }
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
  if (neg) x = -x;
}
inline void writeln(int x) {
  char buffor[21];
  register int i = 0;
  int neg = 0;
  if (x < 0) {
    neg = 1;
    x = -x;
  }
  do {
    buffor[i++] = (x % 10) + '0';
    x /= 10;
  } while (x);
  i--;
  if (neg) putchar('-');
  while (i >= 0) putchar(buffor[i--]);
  putchar('\n');
}
int N, p[100010];
void input() { cin >> N; }
void solve1(int n) {
  if (n % 2 == 1) {
    cout << "NO" << '\n';
    return;
  }
  int s = 1;
  while (s * 2 <= n) s *= 2;
  while (n) {
    int l = s - 1;
    for (int r = s; r <= n; r++) {
      p[l] = r;
      p[r] = l;
      l--;
    }
    n = l;
    while (s > n) s /= 2;
  }
  cout << "YES" << '\n';
  for (int i = 1; i <= N; i++) cout << p[i] << " ";
  cout << '\n';
}
void solve2(int n) {
  if (n % 2 == 1 and n <= 5) {
    cout << "NO" << '\n';
    return;
  }
  if (n == 6) {
    cout << "YES" << '\n';
    cout << 3 << " " << 6 << " " << 1 << " " << 5 << " " << 4 << " " << 2;
    return;
  }
  int s = 1;
  while (s * 2 <= n) s *= 2;
  if (s == n) {
    cout << "NO" << '\n';
    return;
  }
  while (n >= 8) {
    for (int i = n; i >= s + 1; i--) p[i] = i - 1;
    p[s] = n;
    n = s - 1;
    s /= 2;
  }
  p[1] = 7;
  p[2] = 3;
  p[3] = 6;
  p[4] = 5;
  p[5] = 1;
  p[6] = 2;
  p[7] = 4;
  cout << "YES" << '\n';
  for (int i = 1; i <= N; i++) cout << p[i] << " ";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  input();
  solve1(N);
  solve2(N);
  return 0;
}

```