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

Solution:
import java.util.Scanner;

public class F {

    private static final int[] Q6 = {3, 6, 2, 5, 1, 4};

    private static int N;

    public static void main(String[] args) {
        N = new Scanner(System.in).nextInt();

        if (N % 2 == 0) {
            int[] p = new int[N + 1];

            int max = N;
            int pow = Integer.highestOneBit(N);
            while (max > 0) {
                for (int i = 1; pow + i - 1 <= max; i++) {
                    int tmp1 = pow - i;
                    int tmp2 = pow + i - 1;
                    p[tmp1] = tmp2;
                    p[tmp2] = tmp1;
                }
                max = pow - (max - pow + 1) - 1;
                pow = Integer.highestOneBit(max);
            }

            yes(p);
        } else
            System.out.println("NO");

        if (N >= 6 && (N & (-N)) != N) {
            int[] q = new int[N + 1];
            for (int i = 1; i <= N; i++)
                q[i] = i <= 6 ? Q6[i-1] : i;
            for (int i = 7; i <= N; i++) {
                int j = Integer.highestOneBit(i);
                q[i] = q[j];
                q[j] = i;
            }
            yes(q);
        } else
            System.out.println("NO");
    }

    private static void yes(int[] perm) {
        System.out.println("YES");
        for (int i = 1; i <= N; i++)
            System.out.print(perm[i] + " ");
        System.out.println();
    }

}