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.util.Scanner;

public class F455 {

	@SuppressWarnings("resource")
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		int n = input.nextInt();
		if (n % 2 ==1){
			System.out.println("NO");
		}else{
			System.out.println("YES");
			int[] p = new int[n + 1];
			int max = n;
			while (max > 0){
				int i = gpt(max);
				int j = i - 1;
				while (i <= max){
					p[i] = j;
					p[j] = i;
					i++;
					j--;
				}
				max = j;
			}
			for (int i = 1; i <= n; i++){
				System.out.print(p[i] + " ");
			}
			System.out.println();
		}
		//other half
		if (n < 6 || gpt(n) == n){
			System.out.println("NO");
		}else{
			System.out.println("YES");
			if (n == 6){
				System.out.println("5 3 2 6 1 4");
			}else if (n == 7){
				System.out.println("5 3 2 7 1 4 6");
			}else{
				System.out.print("5 3 2 7 1 4 6 ");
				int i = 8;
				int max = i * 2;
				while (max < n){
					while (i < max - 1){
						System.out.print(i + 1 + " ");
						i++;
					}
					System.out.print(max / 2 + " ");
					i = max;
					max = i * 2;
				}
				System.out.print(n + " ");
				i++;
				for (; i <= n; i++){
					System.out.print(i - 1 + " ");
				}
			}
		}
	}
	
	public static int gpt(int n){
		int i = 1;
		while (i * 2 <= n){
			i *= 2;
		}
		return i;
	}

}