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 p[100005], q[100005], k[100005];
void solve(int x) {
  if (x == 0) return;
  int i, l, t = 1;
  while (t * 2 <= x) t <<= 1;
  l = 2 * t - 1 - x;
  for (i = l; i <= x; i++) p[i] = x + l - i;
  solve(l - 1);
}
int main() {
  int i, j, n, t, pos, cnt;
  cin >> n;
  if (n & 1)
    puts("NO");
  else {
    solve(n);
    puts("YES");
    for (i = 1; i <= n; i++) cout << p[i] << " ";
    puts("");
  }
  t = 1;
  while (t * 2 <= n) t = t * 2;
  if (t == n)
    puts("NO");
  else {
    if (n <= 5) puts("NO");
    if (n == 6) {
      puts("YES");
      puts("3 6 1 5 4 2");
    }
    if (n >= 7) {
      q[1] = 7;
      q[2] = 3;
      q[3] = 2;
      q[4] = 5;
      q[5] = 6;
      q[6] = 4;
      q[7] = 1;
      pos = 8;
      while (pos <= n) {
        cnt = 0;
        for (i = pos; i <= min(pos + pos - 1, n); i++) k[++cnt] = i;
        for (j = pos; j < min(pos + pos - 1, n); j++) q[j] = k[j - pos + 2];
        q[min(pos + pos - 1, n)] = k[1];
        pos = min(pos + pos - 1, n) + 1;
      }
      puts("YES");
      for (i = 1; i <= n; i++) cout << q[i] << " ";
      puts("");
    }
  }
  return 0;
}