Problem: Cat Furrier Transform is a popular algorithm among cat programmers to create longcats. As one of the greatest cat programmers ever exist, Neko wants to utilize this algorithm to create the perfect longcat.

Assume that we have a cat with a number x. A perfect longcat is a cat with a number equal 2^m - 1 for some non-negative integer m. For example, the numbers 0, 1, 3, 7, 15 and so on are suitable for the perfect longcats.

In the Cat Furrier Transform, the following operations can be performed on x:

  * (Operation A): you select any non-negative integer n and replace x with x ⊕ (2^n - 1), with ⊕ being a [bitwise XOR operator](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
  * (Operation B): replace x with x + 1. 



The first applied operation must be of type A, the second of type B, the third of type A again, and so on. Formally, if we number operations from one in the order they are executed, then odd-numbered operations must be of type A and the even-numbered operations must be of type B.

Neko wants to produce perfect longcats at industrial scale, thus for each cat Neko only wants to perform at most 40 operations. Can you help Neko writing a transformation plan?

Note that it is not required to minimize the number of operations. You just need to use no more than 40 operations.

Input

The only line contains a single integer x (1 ≤ x ≤ 10^6).

Output

The first line should contain a single integer t (0 ≤ t ≤ 40) — the number of operations to apply.

Then for each odd-numbered operation print the corresponding number n_i in it. That is, print ⌈ t/2 ⌉ integers n_i (0 ≤ n_i ≤ 30), denoting the replacement x with x ⊕ (2^{n_i} - 1) in the corresponding step.

If there are multiple possible answers, you can print any of them. It is possible to show, that there is at least one answer in the constraints of this problem.

Examples

Input


39


Output


4
5 3 

Input


1


Output


0


Input


7


Output


0

Note

In the first test, one of the transforms might be as follows: 39 → 56 → 57 → 62 → 63. Or more precisely:

  1. Pick n = 5. x is transformed into 39 ⊕ 31, or 56. 
  2. Increase x by 1, changing its value to 57. 
  3. Pick n = 3. x is transformed into 57 ⊕ 7, or 62. 
  4. Increase x by 1, changing its value to 63 = 2^6 - 1. 



In the second and third test, the number already satisfies the goal requirement.

Solution (in JAVA):

Solution:
	import java.math.BigInteger;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.InputMismatchException;
	import java.util.Iterator;
	import java.util.LinkedHashSet;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Map;
	import java.util.Map.Entry;
	import java.util.PriorityQueue;
	import java.util.Queue;
	import java.util.Scanner;
	import java.util.Set;
	import java.util.Stack;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStream;
	import java.io.InputStreamReader;
	import java.util.Scanner;
	import java.util.StringTokenizer;
	import java.util.TreeMap;
	import java.util.TreeSet;
	
	public class Main {
										
	//	static FastReader sc= new FastReader();
	static ArrayList<Integer> C;
	static ArrayList<Integer> B;
	static	int mod=(int)1e9+9;
	static long dp[];
	static int k;
	
	static StringBuilder as=new StringBuilder();
	static InputReader rd=new InputReader(System.in);
	
	
	public static void main(String[] args) {
		//HashMap<Long,Long>map =new HashMap<Long, Long>();
				
	
		
		int n=rd.readInt();
		int j=0;
		
		ArrayList<Integer> ans=new ArrayList<Integer>();
		while(!isPowerOfTwo(n+1)) {
			
			int msb=MSB(n);
			//System.out.println(msb);
			n=n^((int)Math.pow(2, msb+1)-1);
			j++;
			ans.add(msb+1);
			//System.out.print((int)Math.pow(2, msb+1)-1);
			//System.out.println(ans);
			if(isPowerOfTwo(n+1))break;
			n++;
			j++;
			

		}
		
		if(ans.size()==0)System.out.println(0);
		
		else {
			System.out.println(j);
		for(int i=0;i<ans.size();i++) {
			System.out.print(ans.get(i)+" ");
			
		}
		System.out.println();
		}
	}
	
	static int MSB(int z) {
		for (int i=20; i>=0; i--) {
			if (((z>>i)&1)!=0) return i;
		}
		return -1;
	}

	
	static long ans=(long)1e18;
	static void dfs(int s,ArrayList<ArrayList<Integer>> adj,boolean []visited,long a[]) {
		
		visited [s]=true;
		ans=Math.min(a[s-1],ans);
		
		for(int i:adj.get(s)) {
			
			if(!visited[i])dfs(i,adj,visited,a);
			
			
		}
		
		
		
		
	}
	
	static boolean isPowerOfTwo (int x) 
	{ 
	  /* First x in the below expression is  
	    for the case when x is 0 */
	    return x!=0 && ((x&(x-1)) == 0); 
	      
	} 
	
			
			//extended Euclidean Algorithm 
			public static int gcd(int a, int b) 
			{ 
			    if (a == 0) 
			        return b; 
			      
			    return gcd(b%a, a); 
			} 
	
	
	static boolean isPrime(int n) { 
	    //check if n is a multiple of 2 
	    if (n%2==0) return false; 
	    //if not, then just check the odds 
	    for(int i=3;i<=Math.sqrt(n);i+=2) { 
	        if(n%i==0) 
	            return false; 
	    } 
	    return true; 
	} 
				static long solve(long n) {
					long sum=(n*(n+1)/2);
					long l=sum/2;
					if(n==3) {
						return 2;
					}
					long k=n;
					if(sum%2==0) {
						long j=n;
						int c=1;
						boolean flag=false;
						long s=0;
						while(j<l) {
							
							n--;
							c++;
							j+=n;
							
							if(j==l) {flag =true;s=n-1;}
							
						}
						long point =l-(j-k);
						long e=0;
						
						if(flag) {
							e=s*(s-1)/2+(k-s)*(k-s-1)/2;
							
						}
						
					//System.out.println(e+" "+c);
						return (c+e);
					}
					else return 0;
					
					
					
				
					
				}
		
		
		static class solver{
			int d;
			double w;
			public solver(int d,double w) {
				
			this.d=d;
			this.w=w;
			
				
			}
			
			
		}
		
		
		
		
		
		
		  static class InputReader {
		        private InputStream stream;
		        private byte[] buf = new byte[1024];
		        private int curChar;
		        private int numChars;
		        private SpaceCharFilter filter;
	
		        public InputReader(InputStream stream) {
		            this.stream = stream;
		        }
	
		        public int read() {
		            if (numChars == -1)
		                throw new InputMismatchException();
		            if (curChar >= numChars) {
		                curChar = 0;
		                try {
		                    numChars = stream.read(buf);
		                } catch (IOException e) {
		                    throw new InputMismatchException();
		                }
		                if (numChars <= 0)
		                    return -1;
		            }
		            return buf[curChar++];
		        }
	
		        public int readInt() {
		            int c = read();
		            while (isSpaceChar(c))
		                c = read();
		            int sgn = 1;
		            if (c == '-') {
	    sgn = -1;
	    c = read();
	}
	int res = 0;
	do {
	    if (c < '0' || c > '9')
	        throw new InputMismatchException();
	    res *= 10;
	    res += c - '0';
	        c = read();
	    } while (!isSpaceChar(c));
	    return res * sgn;
	}
	
	public String readString() {
	    int c = read();
	    while (isSpaceChar(c))
	        c = read();
	    StringBuilder res = new StringBuilder();
	    do {
	        res.appendCodePoint(c);
	        c = read();
	    } while (!isSpaceChar(c));
	    return res.toString();
	}
	
	public boolean isSpaceChar(int c) {
	    if (filter != null)
	        return filter.isSpaceChar(c);
	    return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		        }
	
		        public String next() {
		            return readString();
		        }
	
		    }
		
		  public interface SpaceCharFilter {
		        public boolean isSpaceChar(int ch);
		    }	
		
		
		static int c=0;
	static    void DFSUtil(int s,ArrayList<ArrayList<solver>> adj,int V,boolean visited[],double pw) {
	    	
		
	    	visited[s]=true;
	    	c++;
	    	
	  // 	System.out.print(c+" ");
	
	for(solver i:adj.get(s)) {
		
	
	if(pw>i.w) {
		//System.out.println(pw+" "+i.w+" "+(pw>i.w));
	    		continue;}
	    		
	    		if(!visited[i.d]) {
	    			
	    			DFSUtil(i.d,adj,V,visited,i.w);
	    		}
	    		
	    	}
	    	
	    }
	    
		
		public static <T> ArrayList<T> removeDuplicates(ArrayList<T> list) 
	    { 
	  
	        // Create a new LinkedHashSet 
	        Set<T> set = new LinkedHashSet<>(); 
	  
	        // Add the elements to set 
	        set.addAll(list); 
	  
	        // Clear the list 
	        list.clear(); 
	  
	        // add the elements of set 
	// with no duplicates to the list 
	        list.addAll(set); 
	  
	        // return the list 
			        return list; 
			    } 
	static		class Ungraph{
				
				
				int V,E;
				
				Edge edge[];
				
				class Edge{
					int src,dest;
					
				};
				
					public Ungraph(int v,int e) {
						// TODO Auto-generated constructor stub
	
	V=v;
	
	E=e;
	edge=new Edge[e];
	
	for(int i=0;i<e;i++) {
		edge[i]=new Edge();
		
	}
	
	
	}
	
	class subset{
		
		int parent;
		int rank;
		
	}
	
	int find(subset subsets[],int i) {
		
		if(subsets[i].parent!=i) {
			subsets[i].parent=find(subsets,subsets[i].parent);
		}
		return subsets[i].parent;
	}
	
	
	//finding union
												void Union(subset subsets[],int x,int y) {
													int xroot=find(subsets,x);
													int yroot=find(subsets,y);
													
													if(subsets[xroot].rank<subsets[yroot].rank)subsets[xroot].parent=yroot;
													if(subsets[xroot].rank<subsets[yroot].rank)subsets[yroot].parent=xroot;
													 else
													    { 
													        subsets[xroot].parent = yroot; 
													        subsets[yroot].rank++; 
													    } 
												}
												
												
												  
												
												
												int isCycle(Ungraph graph) {
													
													subset subsets[]=new subset [graph.V];
													
														for(int i=0;i<graph.V;i++) { 	
															 subsets[i] = new subset(); 
															 subsets[i].parent=i;
															 subsets[i].rank=0;
															
														}
														for(int i=0;i<graph.E;i++) {
															int x=find(subsets,graph.edge[i].src);
															int y=find(subsets,graph.edge[i].dest);
															if(x==y)return 1;
															graph.Union(subsets, x, y);
														}
													
													return 0;
													
													
												}
												
											
											
										}
											
											
											
										
											
											
											
											
											
											
											
											
											
								
	}