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 = 100500;
int n;
vector<int> P, Q;
bool espot(int x) {
  while (!(x % 2)) x /= 2;
  return x == 1;
}
void solveP(int n) {
  if (!n) return;
  int m, T = 1;
  while (T * 2 <= n) T *= 2;
  for (int i = (T - 1); i < (int)(n); i++)
    swap(P[i], P[2 * T - 3 - i]), m = 2 * T - 3 - i;
  solveP(m);
}
void shiftQ(int l, int r) {
  int aux = Q[l];
  for (int i = (l); i < (int)(r); i++) Q[i] = Q[i + 1];
  Q[r] = aux;
}
int main() {
  vector<pair<int, int>> pares;
  int l = 8, r = 15;
  for (int i = (0); i < (int)(20); i++) {
    pares.push_back(make_pair(l, r));
    l = r + 1;
    r = l * 2 - 1;
  }
  while (cin >> n) {
    P.resize(n);
    for (int i = (0); i < (int)(n); i++) P[i] = i + 1;
    Q = {7, 3, 2, 6, 4, 5, 1};
    Q.resize(n);
    for (int i = (7); i < (int)(n); i++) Q[i] = i + 1;
    if (n % 2)
      printf("NO\n");
    else {
      solveP(n);
      printf("YES\n");
      for (int i = (0); i < (int)(n); i++) {
        if (i) printf(" ");
        printf("%d", P[i]);
      }
      puts("");
    }
    if (!espot(n) && n > 5) {
      if (n == 6) {
        printf("YES\n5 3 2 6 1 4\n");
        continue;
      }
      for (int i = (0); i < (int)(20); i++) {
        int l = pares[i].first - 1, r = min(pares[i].second, n) - 1;
        if (l > n - 1) break;
        shiftQ(l, r);
      }
      printf("YES\n");
      for (int i = (0); i < (int)(n); i++) {
        if (i) printf(" ");
        printf("%d", Q[i]);
      }
      puts("");
    } else
      printf("NO\n");
  }
  return 0;
}