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, ans[100005], x[21], ta, tb;
set<int> s;
set<int>::iterator it;
int y[100005] = {0, 7, 3, 6, 5, 1, 2, 4};
int main() {
  for (int i = 0; i < 21; i++) x[i] = 1 << i;
  scanf("%d", &n);
  if (n % 2)
    printf("NO\n");
  else {
    printf("YES\n");
    for (int i = 1; i <= n; i++) s.insert(i);
    while (!s.empty()) {
      it = s.end();
      it--;
      ta = *it;
      s.erase(it);
      tb = (1 << 20) - 1;
      while (s.find(ta ^ tb) == s.end()) tb /= 2;
      tb ^= ta;
      ans[ta] = tb;
      ans[tb] = ta;
      s.erase(tb);
    }
    for (int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n ? '\n' : ' ');
  }
  if (n <= 5 || binary_search(x, x + 21, n))
    printf("NO\n");
  else if (n == 6)
    printf("YES\n3 6 2 5 1 4\n");
  else {
    ta = 8, tb = min(n, 15);
    for (int i = 8; i <= n; i++) {
      if (i > tb) ta *= 2, tb = min(tb * 2 + 1, n);
      y[i] = (i + 1 - ta) % (tb - ta + 1) + ta;
    }
    printf("YES\n");
    for (int i = 1; i <= n; i++) printf("%d%c", y[i], i == n ? '\n' : ' ');
  }
  return 0;
}