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 match[100005];
bool solve0(int n, bool outside = 1) {
  if (!n) return 1;
  int nn = n + 1;
  if (nn ^ ((nn) & (-nn)))
    ;
  else
    return 0;
  while (nn ^ ((nn) & (-nn))) nn += ((nn) & (-nn));
  --nn;
  for (int j = n, i = nn - n; i < j; ++i, --j) match[i] = j, match[j] = i;
  if (!solve0(nn - n - 1, 0)) return 0;
  if (outside) {
    cout << "YES" << endl;
    for (int i = 1; i <= n; ++i) cout << match[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; ++i)
      if (match[i] & i) exit(71220);
  }
  return 1;
}
void solve1(int n) {
  if (n < 6 || (((n) & (-n)) == n)) return cout << "NO\n", void();
  if (n == 6) return cout << "YES\n3 6 2 5 1 4\n", void();
  cout << "YES\n3 6 7 5 4 2 1";
  if (n == 7) return cout << endl, void();
  for (int i = 8, j = 15;; i <<= 1, j = (j << 1) + 1) {
    j = min(j, n);
    for (int a = i; a < j; ++a) cout << " " << a + 1;
    cout << " " << i;
    if (j == n) break;
  }
  return cout << endl, void();
}
int main() {
  int n;
  cin >> n;
  if (!solve0(n)) cout << "NO" << endl;
  solve1(n);
}