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 MAXN = 1e6 + 10;
int a[MAXN], n;
bool has[MAXN];
int f(int n) {
  int re = 0;
  while (n != 0) {
    n >>= 1;
    ++re;
  }
  return re;
}
int main() {
  while (scanf("%d", &n) != EOF) {
    memset(has, false, sizeof(has));
    bool flag = true;
    if (n % 2 == 0) {
      for (int i = n; i >= 1; --i) {
        if (!has[i]) {
          int num = f(i);
          num = 1 << num;
          --num;
          num = num ^ i;
          if (!has[num]) {
            has[num] = true;
            a[num] = i;
            has[i] = true;
            a[i] = num;
          } else {
            flag = false;
            break;
          }
        }
      }
      if (flag) {
        printf("YES\n");
        for (int i = 1; i <= n; ++i) {
          printf("%d ", a[i]);
        }
        printf("\n");
      } else {
        printf("NO\n");
      }
    } else {
      printf("NO\n");
    }
    flag = true;
    if (n % 2 == 0) {
      if (n <= 5) {
        printf("NO\n");
      } else {
        int i = 1, num = 1, last = 1;
        while (num + (1 << i) <= n) {
          num = num + (1 << i);
          ++i;
          for (int i = last + 1; i <= (last + num) / 2; ++i) {
            a[i] = num - (i - (last + 1));
            a[num - (i - (last + 1))] = i;
          }
          last = num;
        }
        if (n == num + 1) {
          printf("NO\n");
        } else {
          a[1] = num + 2;
          a[num + 2] = 1;
          a[num + 1] = num + 3;
          a[num + 3] = num + 1;
          for (int i = num + 4; i < n; i += 2) {
            a[i] = i + 1;
            ;
            a[i + 1] = i;
          }
          printf("YES\n");
          for (int i = 1; i <= n; ++i) {
            printf("%d ", a[i]);
          }
          printf("\n");
        }
      }
    } else {
      if (n <= 5) {
        printf("NO\n");
      } else {
        int i = 1, num = 1, last = 1;
        while (num + (1 << i) <= n) {
          num = num + (1 << i);
          ++i;
          for (int i = last + 1; i <= (last + num) / 2; ++i) {
            a[i] = num - (i - (last + 1));
            a[num - (i - (last + 1))] = i;
          }
          last = num;
        }
        for (int j = num + 1; j <= (num + n) / 2; ++j) {
          a[j] = n - (j - (num + 1));
          a[n - (j - (num + 1))] = j;
        }
        a[1] = a[(num + 1 + n) / 2];
        a[(num + 1 + n) / 2] = a[1];
        printf("YES\n");
        a[1] = 7;
        a[2] = 3;
        a[3] = 2;
        a[4] = 6;
        a[5] = 1;
        a[6] = 4;
        a[7] = 5;
        for (int j = 1; j <= n; ++j) {
          printf("%d ", a[j]);
        }
        printf("\n");
      }
    }
  }
  return 0;
}