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;
int n, m, l, r, k, f;
int p[100001];
inline int qr() {
  char ch;
  while ((ch = getchar()) < '0' || ch > '9')
    ;
  int res = ch ^ 48;
  while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + (ch ^ 48);
  return res;
}
inline void one() {
  for (register int i = 16; i; --i) {
    if (m > (l = (1 << i) - 1)) {
      m -= (k = m - l) * 2;
      r = l + 1;
      for (register int j = 1; j <= k; ++j) p[l] = r, p[r] = l, --l, ++r;
    }
  }
  printf("YES ");
  for (register int i = 1; i <= n; ++i) printf("%d ", p[i]);
  puts("");
}
inline void two() {
  printf("YES ");
  if (n & 1) {
    printf("7 3 2 6 1 4 5");
    for (register int i = 8; i <= n; i += 2) printf(" %d %d", i | 1, i);
  } else {
    printf("%d ", n - 1);
    for (register int i = 2; i < n - 2; i += 2) printf("%d %d ", i | 1, i);
    printf("%d 1 %d", n, n - 2);
  }
}
int main() {
  m = n = qr();
  f = 17;
  while (--f)
    if (1 << f == n) break;
  if (n & 1)
    puts("NO");
  else
    one();
  if (f || (n & 1 && n < 7))
    puts("NO");
  else
    two();
  return 0;
}