#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const long long ooo = 9223372036854775807ll;
const int _cnt = 1000 * 1000 + 7;
const int _p = 1000 * 1000 * 1000 + 7;
const int N = 100005;
const double PI = acos(-1.0);
const double eps = 1e-9;
int o(int x) { return x % _p; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
void file_put() {
  freopen("filename.in", "r", stdin);
  freopen("filename.out", "w", stdout);
}
int n, a[N], b[N], x;
int main() {
  scanf("%d", &n);
  a[0] = !((n)&1), b[0] = (n >= 6 && n & (n - 1));
  for (int i = (1); i <= (n); ++i) a[i] = b[i] = i;
  for (int i = n, j; i > 0; i = j - 1) {
    j = i;
    while (j & (j - 1)) j -= (j & (-j));
    j = 2 * j - i - 1;
    if (j)
      for (int k = (j); k <= ((i + j) >> 1); ++k) swap(a[k], a[i + j - k]);
  }
  swap(b[1], b[5]), swap(b[2], b[3]), swap(b[4], b[6]);
  if (n >= 7) swap(b[6], b[7]);
  for (int i = 8; i <= n; i <<= 1) {
    x = (((i << 1) - 1) < (n) ? ((i << 1) - 1) : (n)) - 1;
    for (int j = (i); j <= (x); ++j) swap(b[j], b[j + 1]);
  }
  printf("%s\n", a[0] ? "YES" : "NO");
  if (a[0])
    for (int i = (1); i <= (n); ++i) printf("%d%c", a[i], " \n"[i == n]);
  printf("%s\n", b[0] ? "YES" : "NO");
  if (b[0])
    for (int i = (1); i <= (n); ++i) printf("%d%c", b[i], " \n"[i == n]);
  return 0;
}

### Prompt

In Cpp, your task is to solve 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;
const int oo = 0x3f3f3f3f;
const long long ooo = 9223372036854775807ll;
const int _cnt = 1000 * 1000 + 7;
const int _p = 1000 * 1000 * 1000 + 7;
const int N = 100005;
const double PI = acos(-1.0);
const double eps = 1e-9;
int o(int x) { return x % _p; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
void file_put() {
  freopen("filename.in", "r", stdin);
  freopen("filename.out", "w", stdout);
}
int n, a[N], b[N], x;
int main() {
  scanf("%d", &n);
  a[0] = !((n)&1), b[0] = (n >= 6 && n & (n - 1));
  for (int i = (1); i <= (n); ++i) a[i] = b[i] = i;
  for (int i = n, j; i > 0; i = j - 1) {
    j = i;
    while (j & (j - 1)) j -= (j & (-j));
    j = 2 * j - i - 1;
    if (j)
      for (int k = (j); k <= ((i + j) >> 1); ++k) swap(a[k], a[i + j - k]);
  }
  swap(b[1], b[5]), swap(b[2], b[3]), swap(b[4], b[6]);
  if (n >= 7) swap(b[6], b[7]);
  for (int i = 8; i <= n; i <<= 1) {
    x = (((i << 1) - 1) < (n) ? ((i << 1) - 1) : (n)) - 1;
    for (int j = (i); j <= (x); ++j) swap(b[j], b[j + 1]);
  }
  printf("%s\n", a[0] ? "YES" : "NO");
  if (a[0])
    for (int i = (1); i <= (n); ++i) printf("%d%c", a[i], " \n"[i == n]);
  printf("%s\n", b[0] ? "YES" : "NO");
  if (b[0])
    for (int i = (1); i <= (n); ++i) printf("%d%c", b[i], " \n"[i == n]);
  return 0;
}

```