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;
vector<int> F;
vector<int> sx, sv;
void go(int n) {
  if (n == 0) return;
  int t;
  for (int i = 19; i >= 0; i--) {
    if (n >= (1 << i)) {
      t = i;
      break;
    }
  }
  int sum = (1LL << (t + 1)) - 1;
  for (int i = n; i >= sum - n; i--) {
    F.push_back(sum - i);
  }
  go(sum - n - 1);
}
int main() {
  int n;
  cin >> n;
  if (n % 2 == 1)
    puts("NO");
  else {
    go(n);
    reverse(F.begin(), F.end());
    puts("YES");
    for (int i = 0; i < n; i++) printf("%d%c", F[i], (i == n - 1 ? '\n' : ' '));
  }
  if (n <= 5)
    puts("NO");
  else {
    if (n % 2 == 1) {
      puts("YES");
      sx.push_back(3);
      sx.push_back(6);
      sx.push_back(2);
      sx.push_back(5);
      sx.push_back(1);
      sx.push_back(7);
      sx.push_back(4);
      for (int i = 8; i <= n; i += 2) {
        sx.push_back(i + 1);
        sx.push_back(i);
      }
      for (int i = 0; i < n; i++)
        printf("%d%c", sx[i], (i == n - 1 ? '\n' : ' '));
      for (int i = 0; i < n; i++)
        if (((1 + i) & sx[i]) == 0) assert(0);
    } else {
      sx.push_back(3);
      sx.push_back(6);
      sx.push_back(2);
      sx.push_back(5);
      sx.push_back(1);
      sx.push_back(4);
      bool en = 0;
      for (int i = 3; i <= 17; i++) {
        if (n == (1 << i)) {
          puts("NO");
          en = 1;
        }
      }
      if (!en) {
        puts("YES");
        int nxt = 3;
        int cur = 6;
        while (cur < n) {
          if (cur + 2 == (1 << nxt)) {
            sx.push_back(cur + 3);
            sx.push_back(cur + 4);
            sx.push_back(cur + 1);
            sx.push_back(cur + 2);
            cur += 4;
            nxt++;
          } else {
            sx.push_back(cur + 2);
            sx.push_back(cur + 1);
            cur += 2;
          }
        }
        for (int i = 0; i < n; i++)
          printf("%d%c", sx[i], (i == n - 1 ? '\n' : ' '));
        for (int i = 0; i < n; i++)
          if (((1 + i) & sx[i]) == 0) assert(0);
      }
    }
  }
}