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 q[100005], vis[100005];
int chk[100005];
void permut(int n) {
  int m = n, c = 0, a;
  while (m > 0) {
    c++;
    m >>= 1;
  }
  m = (1 << c) - 1;
  if ((n & 1) == 1) {
    printf("NO\n");
    return;
  }
  printf("YES\n");
  for (int i = 1; i < n + 1; i = i + 1) {
    a = (m ^ i);
    if (a > n || chk[a] == 1) {
      for (int j = c - 1; j > -1; j = j - 1) {
        a &= ((1 << j) - 1);
        if (a <= n && chk[a] == 0) break;
      }
    }
    chk[a] = 1;
    printf("%d ", a);
  }
  printf("\n");
}
int main() {
  int n, a, c = 0, ss;
  bool ff;
  scanf("%d", &n);
  permut(n);
  if (n < 6 || (n - (n & (-n))) == 0)
    printf("NO\n");
  else {
    printf("YES\n");
    if (n == 6) {
      printf("3 6 2 5 1 4");
    } else {
      printf("7 3 6 5 1 2 4 ");
      c = 8;
      ss = 8;
      while (1) {
        a = c + 1;
        if (a > (n + 1)) break;
        if ((a - (a & (-a))) == 0)
          a /= 2;
        else if (a == (n + 1))
          a = ss;
        printf("%d ", a);
        c++;
        if (c > n) break;
        if ((c - (c & (-c))) == 0) ss = c;
      }
    }
    printf("\n");
  }
  return 0;
}