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 S = 100003;
int a[S];
inline void swp(int& x, int& y) { x ^= y, y ^= x, x ^= y; }
int main() {
  register int n, i, j;
  scanf("%d", &n);
  if (n & 1)
    printf("NO");
  else {
    printf("YES");
    for (i = 1; i <= n; ++i) a[i] = i;
    for (i = log2(n); i; --i)
      for (j = 1 << i; a[j] == j; ++j) swp(a[j], a[(1 << i + 1) - 1 - j]);
    for (i = 1; i <= n; ++i) printf(" %d", a[i]);
  }
  putchar('\n');
  if (!(n & 1) || n >= 7) {
    for (i = 1; i <= n; ++i) a[i] = i;
    for (i = 2; i < n; i += 2) swp(a[i], a[i + 1]);
    if (n & 1)
      a[1] = 5, a[5] = 7, a[7] = 1, a[6] = 4, a[4] = 6;
    else if (1 << (int)log2(n) == n) {
      printf("NO");
      return 0;
    } else
      a[n] = n - 2, a[n - 2] = n, a[n - 1] = 1, a[1] = n - 1;
    printf("YES");
    for (i = 1; i <= n; ++i) printf(" %d", a[i]);
  } else
    printf("NO");
  return 0;
}