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 mod = 1e9 + 7;
const int INF = 2147483647;
int a[100005];
int main() {
  int n;
  scanf("%d", &n);
  if (n & 1)
    puts("NO");
  else {
    puts("YES");
    int now = n;
    while (now > 0) {
      int x = 1;
      while (x <= now) x <<= 1;
      x--;
      for (int i = x - now; i <= now; i++) a[i] = x - i;
      now = x - now - 1;
    }
    for (int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
  }
  if (n <= 5)
    puts("NO");
  else {
    if (n & 1) {
      puts("YES");
      for (int i = 3; i <= n; i += 2) a[i] = i ^ 1, a[i ^ 1] = i;
      int m = n - 1;
      if ((m & (-m)) == m)
        a[1] = n - 2, a[n - 3] = n - 5, a[n - 4] = 1;
      else
        a[1] = n, a[n - 1] = n - 3, a[n - 2] = 1;
      for (int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
    } else {
      if ((n & (-n)) == n)
        puts("NO");
      else {
        puts("YES");
        for (int i = 3; i < n; i += 2) a[i] = i ^ 1, a[i ^ 1] = i;
        int x = (n & (-n));
        a[1] = x ^ 1, a[x ^ 1] = 1, a[x] = n, a[n] = x;
        for (int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
      }
    }
  }
  return 0;
}