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:
//package practice.pset1;

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class R455F {

    static int[] arr6 = {3, 6, 1, 5, 4, 2};
    static int[] arr7 = {7, 6, 1, 5, 4, 3, 2};
    static int[] arr9 = {3, 6, 1, 5, 4, 7, 2, 9, 8};
    static int[] arr10 = {3, 6, 1, 5, 4, 2, 9, 10, 7, 8};
    static int[] arr11 = {3, 6, 1, 5, 4, 2, 9, 10, 7, 11, 8};
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        int n = sc.nextInt();
        int[] p = findP(n);
        Pair[] arr = new Pair[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Pair(i+1, i+1);
        }
        q = new int[n+1];
        boolean b = findQ(arr);

        if(p == null)
            pw.println("NO");
        else
        {
            pw.println("YES");
            for (int i = 1; i <= n; i++) {
                if(i != 1)
                    pw.print(" ");
                pw.print(p[i]);
            }
            pw.println();
        }


        if(!b)
            pw.println("NO");
        else
        {
//            if(!check(q))
//                throw new RuntimeException();
            pw.println("YES");
            for (int i = 1; i <= n; i++) {
                if(i != 1)
                    pw.print(" ");
                pw.print(q[i]);
            }
            pw.println();
        }

        pw.flush();
        pw.close();
    }

    static boolean check(int[] arr){
        int cnt = 0;
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            if((i == arr[i]) || ((i) & arr[i]) == 0)
                cnt++;
        }

        return cnt == 0;
    }

    static int[] findP(int n){
        if(n%2 == 1)
            return null;
        int[] ret = new int[n+1];
        for (int x = n; x >= 0; x--) {
            if(ret[x] == 0){
                int y = findComplement(x, bits(x));
                ret[y] = x;
                ret[x] = y;
            }
        }
        return ret;
    }

    static int findComplement(int x, int bits){
        int ret = 0;
        for (int i = 0; i < bits; i++) {
            int lb = (1<<i) & x;
            if(lb == 0)
                ret += 1<<i;
        }

        if((ret & x) != 0)
            System.err.println("BUG in findComplement");
        return ret;
    }

    static int bits(int x){
        int cnt = 0;
        while(x > 0){
            cnt++;
            x/=2;
        }
        return cnt;
    }

    static int[] q;
    static boolean findQ(Pair[] arr){
        int n = arr.length;
        if(n <= 5)
            return false;
        if(Integer.bitCount(n) == 1)
            return false;

        // base cases 6 7 9 10 11
        if(n == 6){
            for (int i = 0; i < arr6.length; i++) {
                int pos = arr[i].orig;
                int val = arr[arr6[i]-1].orig;
                q[pos] = val;
            }
            return true;
        }

        if(n == 7){
            for (int i = 0; i < arr7.length; i++) {
                int pos = arr[i].orig;
                int val = arr[arr7[i]-1].orig;
                q[pos] = val;
            }
            return true;
        }

        if(n == 9){
            for (int i = 0; i < arr9.length; i++) {
                int pos = arr[i].orig;
                int val = arr[arr9[i]-1].orig;
                q[pos] = val;
            }
            return true;
        }

        if(n == 10){
            for (int i = 0; i < arr10.length; i++) {
                int pos = arr[i].orig;
                int val = arr[arr10[i]-1].orig;
                q[pos] = val;
            }
            return true;
        }

        if(n == 11){
            for (int i = 0; i < arr11.length; i++) {
                int pos = arr[i].orig;
                int val = arr[arr11[i]-1].orig;
                q[pos] = val;
            }
            return true;
        }
        // end of base cases

        if(Integer.bitCount(n-1) == 1){
            int i = n-1;
            int j = n-2;
            q[arr[i].orig] = arr[j].orig;
            q[arr[j].orig] = arr[i].orig;
            findQ(Arrays.copyOf(arr, n-2));
        }else{
            ArrayList<Pair> even = new ArrayList<>();
            ArrayList<Pair> odd = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                Pair add = new Pair(arr[i].orig, arr[i].cur/2);
                if(arr[i].cur % 2 == 1){
                    odd.add(add);
                }else{
                    even.add(add);
                }
            }

            odd.add(odd.get(0));
            for (int i = 0; i < odd.size() - 1; i++) {
                Pair x = odd.get(i);
                Pair y = odd.get(i+1);
                q[x.orig] = y.orig;
            }

            Pair[] arr2 = new Pair[even.size()];
            for (int i = 0; i < arr2.length; i++) {
                arr2[i] = even.get(i);
            }
            findQ(arr2);
        }

        return true;
    }

    static class Pair{
        int orig, cur;

        public Pair(int orig, int cur) {
            this.orig = orig;
            this.cur = cur;
        }
    }

    static class Scanner
    {
        StringTokenizer st; BufferedReader br;
        public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
        public Scanner(String s) throws FileNotFoundException {	br = new BufferedReader(new FileReader(new File(s)));}
        public String next() throws IOException {while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());return st.nextToken();}
        public int nextInt() throws IOException {return Integer.parseInt(next());}
        public long nextLong() throws IOException {return Long.parseLong(next());}
        public String nextLine() throws IOException {return br.readLine();}
        public boolean ready() throws IOException {return br.ready();}
    }
}