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 n;
bool step(int first) {
  int val = 0;
  while ((1 << val) < first) val++;
  return (first == (1 << val));
}
int was[1111];
int tt[1111];
void gen(int v) {
  if (v == 26 + 1) {
    for (int i = 1; i <= 26; i++) cout << tt[i] << ' ';
    cout << endl;
  } else {
    if (v == 1) {
      was[14] = 1;
      tt[v] = 14;
      gen(v + 1);
      exit(0);
    }
    if (v == 2) {
      was[13] = 1;
      tt[v] = 13;
      gen(v + 1);
      exit(0);
    }
    for (int i = 1; i <= 26; i++)
      if (was[i] == 0) {
        if ((v & i) != 0) continue;
        if (v == i) continue;
        was[i] = 1;
        tt[v] = i;
        gen(v + 1);
        was[i] = 0;
      }
  }
}
vector<int> ans;
void go(int len) {
  if (len == 0) return;
  if (len == 2) {
    ans.push_back(2);
    ans.push_back(1);
    return;
  }
  if (len == 4) {
    ans.push_back(2);
    ans.push_back(1);
    ans.push_back(4);
    ans.push_back(3);
    return;
  }
  int it = 1;
  int last = 6;
  int ost = -2;
  for (int i = 8; i <= len; i += 2) {
    ost += 2;
    if (ost == last) {
      ost = -2;
      last = i;
    }
  }
  if (ost == -2) ost = 0;
  int save = last;
  for (int i = 0;; i++) {
    ans.push_back(last);
    last--;
    if (last == ost) break;
  }
  for (int i = len; i > save; i--) {
    ans.push_back(i);
  }
  go(ost);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  if (1) {
    if (n % 2 == 1) {
      cout << "NO\n";
    } else {
      cout << "YES\n";
      ans.clear();
      go(n);
      int it = 1;
      for (int first : ans) {
        if ((first & it) != 0 || first == it) cout << n << endl, assert(0);
        it++;
        cout << first << ' ';
      }
      cout << "\n";
    }
  }
  if (1) {
    if (n < 6 || step(n)) {
      cout << "NO\n";
    } else {
      cout << "YES\n";
      vector<int> t = {3, 6, 1, 5, 4, 2};
      if (n == 6) {
        for (int first : t) cout << first << ' ';
        exit(0);
      }
      t = {3, 6, 1, 5, 4, 7, 2};
      for (int i = 8; i <= n;) {
        if (i + 1 <= n) {
          t.push_back(i + 1);
          t.push_back(i);
          i += 2;
        } else {
          int first = t.back();
          t.pop_back();
          t.push_back(i);
          t.push_back(first);
          break;
        }
      }
      int it = 1;
      for (int first : t) {
        if ((first & it) == 0) assert(0);
        it++;
        cout << first << ' ';
      }
    }
  }
  exit(0);
  gen(1);
  exit(0);
  vector<int> t;
  for (int i = 0; i < n; i++) t.push_back(i + 1);
  do {
    bool f = 1;
    for (int i = 0; i < t.size(); i++) {
      if (t[i] == i + 1) {
        f = 0;
        break;
      }
      if ((t[i] & (i + 1)) != 0) {
        f = 0;
        break;
      }
    }
    if (f) {
      for (int i = 0; i < t.size(); i++) cout << t[i] << ' ';
      cout << endl;
    }
  } while (next_permutation(t.begin(), t.end()));
}