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 int mod = (1e9) + 7;
const int siz = (1e5) + 100;
int n;
int p[siz], q[siz];
int six[] = {0, 3, 6, 1, 5, 4, 2};
int seven[] = {0, 3, 6, 1, 5, 4, 7, 2};
void success(int arr[]) {
  printf("YES\n");
  for (int i = 1; i <= n; i++) {
    printf("%d", arr[i]);
    if (i != n)
      printf(" ");
    else
      printf("\n");
  }
}
void fail() { printf("NO\n"); }
bool ispow(int n) {
  int odd = 0;
  while (n != 0) {
    if (n % 2) odd++;
    if (odd > 1) return false;
    n >>= 1;
  }
  return true;
}
int main() {
  scanf("%d", &n);
  bool pv = true, qv = true;
  if (n % 2) {
    pv = false;
  } else {
    int cur = n, lim = n;
    while (cur != 0) {
      int i = 0;
      while ((cur & ~(1 << i)) != 0) cur &= ~(1 << i++);
      int l = cur - 1, u = cur;
      while (true) {
        p[l] = u;
        p[u] = l;
        l--;
        u++;
        if (u > lim) break;
      }
      lim = cur = l;
    }
  }
  if (n < 6 || ispow(n)) {
    qv = false;
  } else {
    if (n == 6) {
      for (int i = 1; i <= n; i++) q[i] = six[i];
    } else {
      for (int i = 1; i <= 7; i++) q[i] = seven[i];
      int last = 8;
      while (true) {
        int i;
        for (i = last; i <= min(n, last * 2 - 1); i++)
          if (i != min(n, last * 2 - 1))
            q[i] = i + 1;
          else
            q[i] = last;
        if (i == n + 1) break;
        last = i;
      }
    }
  }
  if (pv) {
    success(p);
  } else {
    fail();
  }
  if (qv) {
    success(q);
  } else {
    fail();
  }
  return 0;
}