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;
long long bigmod(long long n, long long p) {
  if (p == 0) return 1;
  if (p == 1) return (n + 1000000007) % 1000000007;
  if (p % 2)
    return (bigmod(n, p - 1) * n + 1000000007) % 1000000007;
  else {
    long long x = bigmod(n, p / 2);
    return (x * x + 1000000007) % 1000000007;
  }
}
long long modinverse(long long n) {
  return bigmod(n, 1000000007 - 2) % 1000000007;
}
bool check_2s_power(long long a) {
  return (__builtin_popcountll(a) == 1 ? true : false);
}
long long check_Bit(long long n, long long k) {
  if (n & (1LL << k)) return true;
  return false;
}
long long setBit(long long n, long long k) { return (n | (1LL << k)); }
long long clearBit(long long n, long long k) { return (n & (~(1LL << k))); }
long long toggleBit(long long n, long long k) { return (n ^ (1LL << k)); }
long long visited[100005];
int main() {
  long long n1, n, a, counter = 0, i;
  scanf("%lld", &n);
  bool check = true;
  for (i = n; i > 0; i--) {
    if (visited[i] == 0) {
      n1 = a = i;
      counter = 0;
      while (a != 0) {
        n1 = (toggleBit(n1, counter));
        counter++;
        a /= 2;
      }
      if (visited[n1] != 0 || n1 < 1) {
        check = false;
        goto print_first;
      }
      visited[i] = n1;
      visited[n1] = i;
    }
  }
  cout << "YES" << endl;
  for (i = 1; i <= n; i++) cout << visited[i] << " ";
print_first:
  if (!check) cout << "NO";
  cout << endl;
  if (n < 6 || check_2s_power(n)) {
    cout << "NO" << endl;
    return 0;
  }
  if (n == 6) {
    cout << "YES" << endl << "3 6 2 5 1 4" << endl;
    return 0;
  }
  cout << "YES" << endl << "7 3 6 5 1 2 4 ";
  long long l, r;
  l = 8, r = 2 * l - 1;
  for (;;) {
    if (n < l) return 0;
    r = min(r, n);
    for (i = l + 1; i <= r; i++) cout << i << " ";
    cout << l << " ";
    l *= 2LL;
    r = 2 * l - 1;
  }
}