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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long long N = 1000000 + 10;
long long n, cnt, as[N];
inline long long read() {
  register char ch = getchar();
  register long long x = 0;
  register bool y = 1;
  while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();
  if (ch == '-') ch = getchar(), y = 0;
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
  return y ? x : -x;
}
inline long long lg(long long x) {
  long long d = 0;
  while ((1 << d) <= x) ++d;
  return d - 1;
}
inline void tsk1(long long x) {
  if (x & 1) {
    printf("NO\n");
    return;
  }
  printf("YES\n");
  long long cs = (long long)lg(x), nw = n, gg;
  cnt = 0;
  while (nw > 0) {
    gg = 1 << cs;
    for (register long long i = nw; i >= gg; --i) as[++cnt] = (gg << 1) - 1 - i;
    for (register long long i = gg; i <= nw; ++i) as[++cnt] = i;
    nw = (gg << 1) - 2 - nw;
    cs = (long long)lg(nw);
  }
  for (register long long i = n; i >= 1; --i) printf("%lld ", as[i]);
  printf("\n");
}
inline void tsk2(long long x) {
  if (x == 3 || x == 5 || x == (1 << lg(x))) {
    printf("NO\n");
    return;
  }
  printf("YES\n");
  cnt = 1;
  if (x & 1) {
    cnt = 7;
    as[1] = 7;
    as[2] = 3;
    as[3] = 2;
    as[4] = 6;
    as[5] = 1;
    as[6] = 4;
    as[7] = 5;
  }
  while (cnt <= x) {
    ++cnt;
    as[cnt] = cnt + 1;
    ++cnt;
    as[cnt] = cnt - 1;
  }
  if (!(x & 1)) {
    as[1] = x - 1;
    as[x - 2] = x;
    as[x - 1] = 1;
    as[x] = x - 2;
  }
  for (register long long i = 1; i <= n; ++i) printf("%lld ", as[i]);
}
int main() {
  n = read();
  tsk1(n);
  tsk2(n);
  return 0;
}