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_ {

    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);
        int[] q = findQ(n);
        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(q == null)
            pw.println("NO");
        else
        {
            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 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[] findQ(int n){
        if (n <= 5 || Integer.bitCount(n) == 1)
            return null;
        if(n == 6)
            return new int[]{0, 3, 6, 1, 5, 4, 2};
        if(n == 7)
            return new int[]{0, 7, 6, 1, 5, 4, 3, 2};
        int[] q = new int[n+1];
        int[] arr7 =new int[]{0, 7, 6, 1, 5, 4, 3, 2};
        for (int i = 1; i <= 7; i++)
            q[i] = arr7[i];

        for (int i = 8; i <= n;) {
            ArrayList<Integer> tmp = new ArrayList<>();
            tmp.add(i);
            i++;
            while(i <= n && Integer.bitCount(i) != 1) {
                tmp.add(i);
                i++;
            }
            tmp.add(tmp.get(0));
            for (int j = 0; j < tmp.size()-1; j++) {
                q[tmp.get(j)] = tmp.get(j+1);
            }
        }

        return q;

    }

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