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;
vector<int> ans;
int r[121212], w[121212];
int f(int n) {
  if (n == 0) {
    return 1;
  }
  if (n == 1) return 0;
  if (n == 2) {
    ans.push_back(2);
    ans.push_back(1);
    return 1;
  }
  if (n == 3) return 0;
  if (n == 4) {
    ans.push_back(2);
    ans.push_back(1);
    ans.push_back(4);
    ans.push_back(3);
    return 1;
  }
  if (n == 5) {
    return 0;
  }
  if (n == 6) {
    ans.push_back(6);
    ans.push_back(5);
    ans.push_back(4);
    ans.push_back(3);
    ans.push_back(2);
    ans.push_back(1);
    return 1;
  }
  if (n == 7) return 0;
  int k;
  for (k = 1; k <= n; k *= 2)
    ;
  k /= 2;
  int i;
  for (i = 1; i <= n; i++) r[i] = i, w[i] = i;
  for (i = 1; i < k - 1; i++) r[i] = k - i - 1, w[k - i - 1] = i;
  r[k - 1] = k;
  r[k] = k - 1;
  for (i = k + 1; i <= n; i++) swap(r[i], r[w[i - k]]);
  for (i = 1; i <= k; i++) ans.push_back(r[i]);
  return f(n - k);
}
int main() {
  int n;
  scanf("%d", &n);
  if (n == 1) {
    puts("NO");
    puts("NO");
    return 0;
  }
  if (n == 3) {
    puts("NO");
    puts("NO");
    return 0;
  }
  if (n == 2) {
    puts("YES");
    printf("2 1\n");
    puts("NO");
    return 0;
  }
  int k;
  for (k = 1; k - 2 < n; k *= 2)
    ;
  if (k - 2 == n) {
    puts("YES");
    for (int i = n; i >= 1; i--) printf("%d ", i);
    puts("");
  } else {
    for (k = 1; k - 1 < n; k *= 2)
      ;
    if (n != k) {
      if (f(n)) {
        puts("YES");
        for (auto x : ans) printf("%d ", x);
        puts("");
      } else
        puts("NO");
    } else {
      puts("NO");
    }
  }
  for (k = 1; k < n; k *= 2)
    ;
  if (n == k) {
    puts("NO");
    return 0;
  }
  if (n == 5) {
    puts("NO");
    return 0;
  }
  if (n == 6) {
    puts("YES");
    puts("3 6 2 5 1 4");
    return 0;
  }
  if (n == 7) {
    puts("YES");
    puts("3 6 2 7 1 4 5");
    return 0;
  }
  k /= 2;
  puts("YES");
  int i;
  for (i = 1; i < k / 2 - 1; i++) printf("%d ", i + k / 2);
  printf("%d %d %d ", 1, k - 1, k / 2);
  for (i = 2; i <= k / 2 - 1; i++) printf("%d ", i);
  for (i = k; i < n; i++) printf("%d ", i + 1);
  printf("%d ", k);
  return 0;
}