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

public class utkarsh{
	BufferedReader br;
	PrintWriter out;

	void solve(){
		br = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		
		int n = ni();

		if(n%2 == 1){
			out.println("NO");
		}else{
			out.println("YES");
			int a[] = new int[n+1];
			int l, r, m = n;
			while(m > 0){
				//System.out.println(m);
				r = 1;
				while(r <= m)	r <<= 1;
				r >>= 1;
				l = r-1;
				while(r <= m){
					a[l] = r;
					a[r] = l;
					r++;
					l--;
				}
				m = l;
			}
			for(int i = 1; i <= n; i++)	out.print(a[i] + " ");
			out.println();
		}

		if(n <= 5 || (n & (n-1)) == 0){
			out.println("NO");
		}else if(n == 6){
			out.println("YES\n3 6 2 5 1 4");
		}else if(n == 7){
			out.println("YES\n7 3 6 5 1 2 4");
		}else{
			out.println("YES\n7 3 6 5 1 2 4 ");
			int x = 8;
			while(true){
				int m = Math.min(n, x - 1 + x);
				out.print(m + " ");
				for(int i = x; i < m; i++)	out.print(i + " ");
				if(m == n)	break;
				x <<= 1;
			}
			out.println();
		}

		out.flush();
	}

	int ni(){
		return Integer.parseInt(ns());
	}

	String ip[];
	int len, sz;

	String ns(){
		if(len >= sz){
			try{
				ip = br.readLine().split(" ");
				len = 0;
				sz = ip.length;
			}catch(IOException e){
				throw new InputMismatchException();
			}
			if(sz <= 0)	return "-1";
		}
		return ip[len++];
	}

	public static void main(String[] args){	new utkarsh().solve();	}
}