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

public class C {

	public Object solve() {
		int N = sc.nextInt();

		int [] res = new int [N];
		int F = 1, J = 0;

		while (N > 0) {
			if (N == 3) {
				res[J++] = F;
				res[J++] = F;
				res[J++] = 3*F;
				break;
			}
			int D = N - N/2;
			for (@SuppressWarnings("unused") int i : rep(D))
				res[J++] = F;
			N /= 2; F *= 2;
		}

		return exit(res);
	}

	private static final boolean ONE_TEST_CASE = true;

	private static void init() {
	}

	private static Iterable<Integer> rep (int N) { return rep(0, N); }
	private static Iterable<Integer> rep (final int S, final int T) { return new Iterable<Integer>() { public Iterator<Integer> iterator() { return S < T ? java.util.stream.IntStream.range(S,  T).iterator() : Collections.emptyIterator(); } }; }
	////////////////////////////////////////////////////////////////////////////////////
	private static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static Object print (Object o, Object ... A) { IOUtils.print(o, A); return null; }
	private static Object exit (Object o, Object ... A) { print(o, A); IOUtils.exit(); return null; }
	private static class IOUtils {
		public static class MyScanner {
			public String next() { newLine(); return line[index++]; }
			public int nextInt() { return Integer.parseInt(next()); }
			//////////////////////////////////////////////
			private boolean eol() { return index == line.length; }
			private String readLine() {
				try {
					return r.readLine();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private final java.io.BufferedReader r;
			private MyScanner () { this(new java.io.BufferedReader(new java.io.InputStreamReader(System.in))); }
			private MyScanner (java.io.BufferedReader r) {
				try {
					this.r = r;
					while (!r.ready())
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine() {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private String [] split(String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build(Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim(String delim, Object o, Object ... A) {
			StringBuilder b = new StringBuilder();
			append(b, o, delim);
			for (Object p : A)
				append(b, p, delim);
			return b.substring(delim.length());
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static final java.text.DecimalFormat formatter = new java.text.DecimalFormat("#.#########");
		private static void start() { if (t == 0) t = millis(); }
		private static void append(java.util.function.Consumer<Object> f, java.util.function.Consumer<Object> g, final Object o) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					f.accept(java.lang.reflect.Array.get(o, i));
			}
			else if (o instanceof Iterable<?>)
				((Iterable<?>)o).forEach(f::accept);
			else
				g.accept(o instanceof Double ? formatter.format(o) : o);
		}
		private static void append(final StringBuilder b, Object o, final String delim) {
			append(x -> { append(b, x, delim); }, x -> b.append(delim).append(x), o);
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static Object print(Object o, Object ... A) { pw.println(build(o, A)); return null; }
		private static void err(Object o, Object ... A) { System.err.println(build(o, A)); }
		private static boolean PRINT;
		private static void write(Object o) {
			err(o, '(', time(), ')');
			if (PRINT)
				pw.println(o);
		}
		private static void exit() {
			IOUtils.pw.close();
			System.out.flush();
			err("------------------");
			err(time());
			System.exit(0);
		}
		private static long t;
		private static long millis() { return System.currentTimeMillis(); }
		private static String time() { return "Time: " + (millis() - t) / 1000.0; }
		private static void run(int N) {
			try { PRINT = System.getProperties().containsKey("PRINT"); }
			catch (Throwable t) {}

			for (int n = 1; n <= N; ++n) {
				Object res = new C().solve();
				if (res != null)
					write("Case #" + n + ": " + build(res));
			}
			exit();
		}
	}
	public static void main(String[] args) {
		init();
		int N = ONE_TEST_CASE ? 1 : sc.nextInt();
		IOUtils.run(N);
	}
}
