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 mm[100050];
int ans1[100050], ans2[100050];
int N;
void init_mm() {
  mm[0] = -1;
  for (int i = 1; i < 100050; ++i)
    mm[i] = ((i & (i - 1)) == 0 ? mm[i - 1] + 1 : mm[i - 1]);
}
void work1(int& up) {
  int mid = 1 << mm[up];
  int bound = up - mid + 1;
  up -= 2 * bound;
  for (int i = 1; i <= bound; ++i) {
    ans1[mid + i - 1] = mid - i;
    ans1[mid - i] = mid + i - 1;
  }
}
void work2(int up) {
  if (up == 6) {
    ans2[1] = 3, ans2[2] = 6, ans2[3] = 2, ans2[4] = 5, ans2[5] = 1,
    ans2[6] = 4;
    return;
  }
  if (up >= 7) {
    ans2[1] = 5, ans2[2] = 3, ans2[3] = 2, ans2[4] = 7, ans2[5] = 6,
    ans2[6] = 4, ans2[7] = 1;
  }
  int low = 1 << 3, high = (low << 1) - 1;
  while (high <= up) {
    ans2[low] = high;
    for (int i = low + 1; i <= high; ++i) ans2[i] = i - 1;
    low = low << 1;
    high = (low << 1) - 1;
  }
  if (low < up) {
    ans2[low] = up;
    for (int i = low + 1; i <= up; ++i) ans2[i] = i - 1;
  }
}
int main() {
  init_mm();
  while (scanf("%d", &N) == 1) {
    bool judge1 = true, judge2 = true;
    if (N & 1) judge1 = false;
    if (judge1) {
      int up = N;
      while (up) {
        work1(up);
      }
    }
    if (N <= 5 || (N & (N - 1)) == 0) judge2 = false;
    if (judge2) {
      int up = N;
      work2(up);
    }
    printf("%s\n", judge1 ? "YES" : "NO");
    if (judge1) {
      for (int i = 1; i <= N; ++i) printf("%d%c", ans1[i], i == N ? '\n' : ' ');
    }
    printf("%s\n", judge2 ? "YES" : "NO");
    if (judge2) {
      for (int i = 1; i <= N; ++i) {
        printf("%d%c", ans2[i], i == N ? '\n' : ' ');
      }
    }
  }
  return 0;
}