#include <bits/stdc++.h>
const int N = 100005;
int n, a[N];
bool solve1(int n) {
  if (n & 1) return 0;
  int t = 1;
  while (t <= n) t <<= 1;
  for (int i = t - n - 1; i <= n; i++) a[i] = t - 1 - i;
  if (t - n - 2) return solve1(t - n - 2);
  return 1;
}
bool solve2(int n) {
  if (__builtin_popcount(n) == 1) return 0;
  if (n <= 5) return 0;
  puts("YES");
  if (n & 1) {
    printf("3 6 1 5 7 2 4 ");
    for (int i = 8; i <= n; i += 2) printf("%d %d ", i + 1, i);
  } else {
    printf("%d ", n - 1);
    for (int i = 2; i <= n - 3; i += 2) printf("%d %d ", i + 1, i);
    printf("%d %d %d\n", n, 1, n - 2);
  }
  return 1;
}
int main() {
  scanf("%d", &n);
  if (solve1(n)) {
    puts("YES");
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    puts("");
  } else
    puts("NO");
  if (!solve2(n)) puts("NO");
}

### Prompt

Please create a solution in cpp to the following 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

### Response

```cpp
#include <bits/stdc++.h>
const int N = 100005;
int n, a[N];
bool solve1(int n) {
  if (n & 1) return 0;
  int t = 1;
  while (t <= n) t <<= 1;
  for (int i = t - n - 1; i <= n; i++) a[i] = t - 1 - i;
  if (t - n - 2) return solve1(t - n - 2);
  return 1;
}
bool solve2(int n) {
  if (__builtin_popcount(n) == 1) return 0;
  if (n <= 5) return 0;
  puts("YES");
  if (n & 1) {
    printf("3 6 1 5 7 2 4 ");
    for (int i = 8; i <= n; i += 2) printf("%d %d ", i + 1, i);
  } else {
    printf("%d ", n - 1);
    for (int i = 2; i <= n - 3; i += 2) printf("%d %d ", i + 1, i);
    printf("%d %d %d\n", n, 1, n - 2);
  }
  return 1;
}
int main() {
  scanf("%d", &n);
  if (solve1(n)) {
    puts("YES");
    for (int i = 1; i <= n; i++) printf("%d ", a[i]);
    puts("");
  } else
    puts("NO");
  if (!solve2(n)) puts("NO");
}

```