Let's call the following process a transformation of a sequence of length n.

If the sequence is empty, the process ends. Otherwise, append the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) (GCD) of all the elements of the sequence to the result and remove one arbitrary element from the sequence. Thus, when the process ends, we have a sequence of n integers: the greatest common divisors of all the elements in the sequence before each deletion.

You are given an integer sequence 1, 2, ..., n. Find the lexicographically maximum result of its transformation.

A sequence a_1, a_2, …, a_n is lexicographically larger than a sequence b_1, b_2, …, b_n, if there is an index i such that a_j = b_j for all j < i, and a_i > b_i.

Input

The first and only line of input contains one integer n (1≤ n≤ 10^6).

Output

Output n integers — the lexicographically maximum result of the transformation.

Examples

Input

3


Output

1 1 3 

Input

2


Output

1 2 

Input

1


Output

1 

Note

In the first sample the answer may be achieved this way:

  * Append GCD(1, 2, 3) = 1, remove 2. 
  * Append GCD(1, 3) = 1, remove 1. 
  * Append GCD(3) = 3, remove 3. 



We get the sequence [1, 1, 3] as the result.
import java.io.*;
import java.util.*;

public class CodeForces{
    /*****************************************WRITING CODE STARTS HERE******************************************/

    public static void solve(int tCase)throws IOException {
       int n = sc.nextInt();;
       int remain = n;
       int curr = 1;
       while (remain>0){
           if(remain == 3){
               out.println(curr+" "+curr+" "+3*curr);
               break;
           }
           int count = (1+remain)>>1;
           for(int i=0;i<count;i++) out.print(curr+" ");
           remain-=count;
           curr<<=1;
       }
    }



    /*****************************************WRITING CODE ENDS HERE******************************************/

    public static void main(String[] args) throws IOException{
        int testCase = 1;
//        testCase = sc.nextInt();
        for (int i = 1; i <= testCase; i++) solve(i);
        closeIO();
    }
    static FastestReader sc = new FastestReader();              // FASTEST INPUT
    static PrintWriter out = new PrintWriter(System.out);                // FAST OUTPUT


    /**************************************HELPER FUNCTION STARTS HERE ************************************/

    public static int mod = (int) 1e9 +7;
    public static  int inf_int = (int) 1e9;
    public static  long inf_long = (long) 1e18;

    public static final String YES = "YES";
    public static final String NO = "NO";

    // euclidean algorithm time O(max (loga ,logb))
    public static long _gcd(long a, long b) {
        long x = Math.min(a, b);
        long y = Math.max(a, b);
        if (y % x == 0) return x;
        return _gcd(y % x, x);
    }

    public static long _lcm(long a, long b) {
        // lcm(a,b) * gcd(a,b) = a * b
        return (a / _gcd(a, b)) * b;
    }
    // binary exponentiation time O(logn)
    public static long _power(long x, long n) {
        long ans = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                ans *= x;
                ans %= mod;
                n--;
            } else {
                x *= x;
                x %= mod;
                n >>= 1;
            }
        }
        return ans;
    }

    public static long _firstDivisor(long n) {
        if (n == 1 || n == 0) return n;
        for (long i = 2; i * i <= n; i++)
            if (n % i == 0) return i;
        return -1;
    }


    /**************************************HELPER FUNCTION ENDS HERE ************************************/

    /*****************************************FAST INPUT STARTS HERE *************************************/


    public static void closeIO() throws IOException{
        out.flush();
        out.close();
        sc.close();
    }
    private static class FastestReader {
        private static final int BUFFER_SIZE = 1 << 16;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastestReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastestReader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }

        private int skip() throws IOException {
            int b;
            //noinspection StatementWithEmptyBody
            while ((b = read()) != -1 && isSpaceChar(b)) {}
            return b;
        }

        public String next() throws IOException {
            int b = skip();
            final StringBuilder sb = new StringBuilder();
            while (!isSpaceChar(b)) { // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = read();
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            final boolean neg = c == '-';
            if (neg) { c = read(); }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg) { return -ret; }
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ') { c = read(); }
            final boolean neg = c == '-';
            if (neg) { c = read(); }
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg) { return -ret; }
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ') { c = read(); }
            final boolean neg = c == '-';
            if (neg) { c = read(); }

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg) { return -ret; }
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1) { buffer[0] = -1; }
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead) { fillBuffer(); }
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            din.close();
        }

    }
    /*****************************************FAST INPUT ENDS HERE *************************************/
}