#include <bits/stdc++.h>
using namespace std;
int n, p2[30];
int q[100005], p[100005];
inline void init() {
  p2[0] = 1;
  for (int i = 1; i <= n; i++) p[i] = q[i] = i;
  for (int i = 1; i < 30; i++) p2[i] = p2[i - 1] * 2;
}
inline void solveP() {
  bool flag = 1;
  for (int i = n; i > 0;) {
    int k = *upper_bound(p2, p2 + 30, i);
    int j = (k - 1) ^ i;
    if (j == 0) flag = 0;
    reverse(p + j, p + i + 1);
    i = j - 1;
  }
  if (flag) {
    puts("YES");
    for (int i = 1; i <= n; i++) printf("%d%c", p[i], i == n ? '\n' : ' ');
  } else {
    puts("NO");
  }
}
inline void solveQ() {
  if ((n & (n - 1)) == 0 || n < 6) {
    puts("NO");
  } else if (n == 6) {
    puts("YES");
    puts("3 6 2 5 1 4");
  } else {
    puts("YES");
    int s[] = {0, 7, 3, 2, 5, 6, 4, 1};
    for (int i = 1; i <= 7; i++) q[i] = s[i];
    for (int i = 8; i < n;) {
      int k = *upper_bound(p2, p2 + 30, i);
      int j = min(k - 1, n);
      for (int g = i; g < j; g++) q[g] = q[g + 1];
      q[j] = i;
      i = j + 1;
    }
    for (int i = 1; i <= n; i++) printf("%d%c", q[i], i == n ? '\n' : ' ');
  }
}
int main() {
  scanf("%d", &n);
  init();
  solveP();
  solveQ();
  return 0;
}

### Prompt

Generate 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;
int n, p2[30];
int q[100005], p[100005];
inline void init() {
  p2[0] = 1;
  for (int i = 1; i <= n; i++) p[i] = q[i] = i;
  for (int i = 1; i < 30; i++) p2[i] = p2[i - 1] * 2;
}
inline void solveP() {
  bool flag = 1;
  for (int i = n; i > 0;) {
    int k = *upper_bound(p2, p2 + 30, i);
    int j = (k - 1) ^ i;
    if (j == 0) flag = 0;
    reverse(p + j, p + i + 1);
    i = j - 1;
  }
  if (flag) {
    puts("YES");
    for (int i = 1; i <= n; i++) printf("%d%c", p[i], i == n ? '\n' : ' ');
  } else {
    puts("NO");
  }
}
inline void solveQ() {
  if ((n & (n - 1)) == 0 || n < 6) {
    puts("NO");
  } else if (n == 6) {
    puts("YES");
    puts("3 6 2 5 1 4");
  } else {
    puts("YES");
    int s[] = {0, 7, 3, 2, 5, 6, 4, 1};
    for (int i = 1; i <= 7; i++) q[i] = s[i];
    for (int i = 8; i < n;) {
      int k = *upper_bound(p2, p2 + 30, i);
      int j = min(k - 1, n);
      for (int g = i; g < j; g++) q[g] = q[g + 1];
      q[j] = i;
      i = j + 1;
    }
    for (int i = 1; i <= n; i++) printf("%d%c", q[i], i == n ? '\n' : ' ');
  }
}
int main() {
  scanf("%d", &n);
  init();
  solveP();
  solveQ();
  return 0;
}

```