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.io.IOException;
import java.util.*;

public class Test {
    int readInt() {
        int ans = 0;
        boolean neg = false;
        try {
            boolean start = false;
            for (int c = 0; (c = System.in.read()) != -1; ) {
                if (c == '-') {
                    start = true;
                    neg = true;
                    continue;
                } else if (c >= '0' && c <= '9') {
                    start = true;
                    ans = ans * 10 + c - '0';
                } else if (start) break;
            }
        } catch (IOException e) {
        }
        return neg ? -ans : ans;
    }

    int[] ns;

    void swap(int i, int j) {
        int t = ns[i];
        ns[i] = ns[j];
        ns[j] = t;
    }

    void start() {
        int n = readInt();
        ns = new int[n+1];
        if (n % 2 == 1) System.out.println("NO");
        else {
            System.out.println("YES");
            for (int i = n; i >= 1; i--) {
                if (ns[i] != 0) continue;
                int one = Integer.highestOneBit(i);
                int k = ~i & (one - 1);
                ns[i] = k;
                ns[k] = i;
            }
            for (int i = 1; i <= n; i++) {
                System.out.print(ns[i] + " ");
            }
            System.out.println();
        }
        Arrays.fill(ns, 0);
        if (n < 6 || (n & (n - 1)) == 0) System.out.println("NO");
        else {
            System.out.println("YES");
            for (int i = 1; i <= Math.min(7, n); i++) ns[i] = i;
            swap(5, 1);
            swap(2, 3);
            swap(4, 6);
            if (n >= 7) {
                swap(7, 1);
            }
            for (int i = 8; i <= n;) {
                int ni = i << 1;
                int j = 0;
                for (j = i + 1; j < ni && j <= n; j++) ns[j] = j - 1;
                ns[i] = j - 1;
                i = j;
            }
            for (int i = 1; i <= n; i++) System.out.print(ns[i] + " ");
            System.out.println();
        }
    }

    public static void main(String[] args) {

        new Test().start();

    }
}