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 num[100005];
bool life[100005];
int init[25];
int lowbit(int x) { return -x & x; }
int main() {
  int n, x;
  init[1] = 1;
  for (int i = 2; i <= 20; i++) init[i] = init[i - 1] * 2;
  scanf("%d", &n);
  if (n % 2)
    printf("NO\n");
  else {
    printf("YES\n");
    for (int i = n; i; i -= 2) {
      for (int j = 20; j; j--) {
        x = init[j] - i - 1;
        if (x > 0 && x < n && !life[x]) {
          num[i] = x;
          num[x] = i;
          life[x] = 1;
          break;
        }
      }
    }
    for (int i = 1; i <= n; i++) {
      printf("%d", num[i]);
      if (i == n)
        printf("\n");
      else
        printf(" ");
    }
  }
  if (n < 6 || lowbit(n) == n)
    printf("NO\n");
  else {
    printf("YES\n");
    if (n == 6)
      printf("3 6 2 5 1 4\n");
    else {
      if (n == 7)
        printf("3 6 2 7 1 4 5\n");
      else {
        printf("3 6 2 7 1 4 5");
        x = 7;
        for (int i = 1; i <= 20; i++) {
          if (init[i] - 1 > x && x < n) {
            for (int j = x + 1; j < init[i] - 1 && j < n; j++)
              printf(" %d", j + 1);
            printf(" %d", x + 1);
            x = min(n, init[i] - 1);
          }
        }
        printf("\n");
      }
    }
  }
  return 0;
}