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;
    }

    void start() {
        int n = readInt();
        int[] 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");
            int m = n;
            if (((n - 1) & ( n - 2)) == 0) {
                ns[n] = n - 1;
                ns[n - 1] = n;
                n -= 3;
            } else if (n % 2 == 1) n--;
            int one = Integer.lowestOneBit(n);
            ns[one] = n;
            ns[n] = one;
            if (one != 1) {
                int k = (one << 1) - 1;
                ns[1] = k;
                ns[k] = 1;
            }
            for (int i = 1; i <= n; i++) {
                if (ns[i] != 0) continue;
                ns[i] = i + 1;
                ns[i + 1] = i;
            }
            if (((m - 1) & (m - 2)) == 0) {
                int t = ns[1];
                ns[1] = m - 2;
                ns[m - 2] = t;
            } else if (m % 2 == 1) {
                int t = ns[1];
                ns[1] = m;
                ns[m] = t;
            }
            for (int i = 1; i <= m; i++) {
                System.out.print(ns[i] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {

        new Test().start();

    }
}