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 PYTHON3):

Solution:

from math import log2
n = int(input())
p = [0] * (n + 1)
def f(n):
    k = int(log2(n))
    while k:
        i = 1
        while (1 << k) + i - 1 <= n:
            p[(1 << k) + i - 1] = (1 << k) - i
            p[(1 << k) - i] = (1 << k) + i - 1
            i += 1
        n = (1 << k) - i
        if not n:
            break
        k = int(log2(n))
if n & 1:
    print('NO')
else:
    print('YES')
    f(n)
    print(*p[1:])

if n < 6 or 1 << int(log2(n)) == n:
    print('NO')
else:
    print('YES')
    if n == 6:
        print('3 6 2 5 1 4')
    elif n == 7:
        print('7 3 6 5 1 2 4')
    else:
        print('7 3 6 5 1 2 4', end=' ')
        k = 3
        while (1 << k) < n:
            for i in range((1 << k) + 1, min(1 << k + 1, n + 1)):
                print(i, end=' ')
            print(1 << k, end=' ')
            k += 1