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;
bool pt(int n) { return (n & (n - 1)) == 0; }
void q(int n) {
  if (pt(n) || n < 6) {
    cout << "NO" << endl;
    return;
  }
  if (n == 6) {
    cout << "YES" << endl;
    cout << "3 6 1 5 4 2" << endl;
    return;
  } else if (n == 7) {
    cout << "YES" << endl;
    cout << "3 6 1 5 4 7 2" << endl;
    return;
  }
  vector<int> v = {0, 3, 6, 1, 5, 4, 7, 2, 9, 8};
  int w = 6;
  for (int i = 10; i <= n; i++) {
    v.push_back(i);
    if (pt(i)) continue;
    sort(v.begin() + (i - w), v.end());
    bool b = true;
    do {
      b = true;
      for (int i = v.size() - w - 1; i < v.size(); i++) {
        if (v[i] == i || (v[i] & i) == 0) b = false;
        if (!b) break;
      }
      if (b) break;
    } while (next_permutation(v.begin() + (i - w), v.end()));
  }
  cout << "YES" << endl;
  for (int i = 1; i <= n; i++) cout << v[i] << " ";
  cout << endl;
}
void f(int n) {
  if (n % 2) {
    cout << "NO" << endl;
    return;
  }
  cout << "YES" << endl;
  vector<int> v = {0, 2, 1};
  int lp = 2;
  for (int i = 4; i <= n; i += 2) {
    v.push_back(i);
    v.push_back(i - 1);
    while (v[i - 1] == i - 1 || (v[i - 1] & (i - 1))) {
      swap(v[i - 1], v[(i - 1) ^ (v[i - 1] & (i - 1))]);
    }
    while (v[i] == i || (v[i] & i)) {
      swap(v[i], v[i ^ (v[i] & i)]);
    }
  }
  for (int i = 1; i <= n; i++) cout << v[i] << " ";
  cout << endl;
}
int main() {
  int n;
  cin >> n;
  f(n);
  q(n);
}