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;
const int inf = 1e9;
const long long inf_ll = 1e18;
vector<int> a(int n) {
  if (n == 0) return {};
  int x = (1 << (31 - __builtin_clz(n))) - 1;
  auto p = a(2 * x - n);
  for (int i = 0; i < 2 * n - 2 * x; i++) p.push_back(n - i);
  return p;
}
vector<int> b(int n) {
  if (n == 6) return {3, 6, 2, 5, 1, 4};
  vector<int> p = {5, 3, 2, 7, 1, 4, 6};
  for (int i = 8; i <= n; i++)
    p.push_back(__builtin_popcount(i) == 1 ? min(n, 2 * i - 1) : i - 1);
  return p;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  if (n & 1)
    cout << "NO\n";
  else {
    cout << "YES\n";
    auto p = a(n);
    for (int i = 0; i < n; i++) cout << p[i] << " \n"[i == n - 1];
  }
  if (n < 6 || __builtin_popcount(n) == 1)
    cout << "NO\n";
  else {
    cout << "YES\n";
    auto p = b(n);
    for (int i = 0; i < n; i++) cout << p[i] << " \n"[i == n - 1];
  }
}