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.
#include <bits/stdc++.h>
const int _ML = 228;
const char _inpf[] = "";
const char _outf[] = "";
#pragma GCC optimize("O3,no-stack-protector")
using namespace std;
const double PI = 3.14159265358979323846;
mt19937 rd(228);
template <class T, class U>
inline ostream &operator<<(ostream &, const pair<T, U> &);
template <class T, class U>
inline istream &operator>>(istream &, pair<T, U> &);
template <class T>
inline ostream &operator<<(ostream &, const vector<T> &);
template <class T>
inline istream &operator>>(istream &, vector<T> &);
template <class T>
inline ostream &operator<<(ostream &, const set<T> &);
template <class T>
inline ostream &operator<<(ostream &, const multiset<T> &);
template <class T>
inline ostream &operator<<(ostream &, const unordered_set<T> &);
template <class T>
inline ostream &operator<<(ostream &, const unordered_multiset<T> &);
template <class T, class U>
inline ostream &operator<<(ostream &, const map<T, U> &);
template <class T, class U>
inline ostream &operator<<(ostream &, const unordered_map<T, U> &);
int mul = 1;
vector<int> ans;
void f(vector<int> &a) {
  if ((int)(a).size() >= 100) {
    vector<int> b;
    for (int i : a) {
      if (i % 2 == 0) {
        b.push_back(i / 2);
      } else {
        ans.push_back(mul);
      }
    }
    mul *= 2;
    a = b;
    return;
  }
  map<int, int> cnt;
  for (int i : a) {
    for (int j = 2; j * j <= i; ++j) {
      if (i % j == 0) {
        ++cnt[j];
        while (i % j == 0) {
          i /= j;
        }
      }
    }
    if (i != 1) {
      ++cnt[i];
    }
  }
  pair<int, int> mx;
  for (auto i : cnt) {
    if (i.second > mx.second || (i.second == mx.second && i.first > mx.first)) {
      mx = i;
    }
  }
  vector<int> b;
  for (int i : a) {
    if (i % mx.first == 0) {
      b.push_back(i / mx.first);
    } else {
      ans.push_back(mul);
    }
  }
  mul *= mx.first;
  a = b;
}
inline void _main_function() {
  int n;
  cin >> n;
  vector<int> a(n);
  iota((a).begin(), (a).end(), 1);
  for (; (int)(a).size() >= 2;) {
    f(a);
  }
  ans.push_back(mul);
  cout << ans << '\n';
}
int main() {
  if (_inpf[0] != '\0') assert(freopen(_inpf, "r", stdin) != nullptr);
  if (_outf[0] != '\0') assert(freopen(_outf, "w", stdout) != nullptr);
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << setprecision(20);
  _main_function();
}
template <class T, class U>
inline ostream &operator<<(ostream &_out, const pair<T, U> &_p) {
  _out << _p.first << ' ' << _p.second;
  return _out;
}
template <class T, class U>
inline istream &operator>>(istream &_in, pair<T, U> &_p) {
  _in >> _p.first >> _p.second;
  return _in;
}
template <class T>
inline ostream &operator<<(ostream &_out, const vector<T> &_v) {
  if (_v.empty()) {
    return _out;
  }
  _out << *_v.begin();
  for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <class T>
inline istream &operator>>(istream &_in, vector<T> &_v) {
  for (auto &_i : _v) {
    _in >> _i;
  }
  return _in;
}
template <class T>
inline ostream &operator<<(ostream &_out, const set<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <class T>
inline ostream &operator<<(ostream &_out, const multiset<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <class T>
inline ostream &operator<<(ostream &_out, const unordered_set<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <class T>
inline ostream &operator<<(ostream &_out, const unordered_multiset<T> &_s) {
  if (_s.empty()) {
    return _out;
  }
  _out << *_s.begin();
  for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) {
    _out << ' ' << *_it;
  }
  return _out;
}
template <class T, class U>
inline ostream &operator<<(ostream &_out, const map<T, U> &_m) {
  if (_m.empty()) {
    return _out;
  }
  _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')';
  for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) {
    _out << ", (" << _it->first << ": " << _it->second << ')';
  }
  return _out;
}
template <class T, class U>
inline ostream &operator<<(ostream &_out, const unordered_map<T, U> &_m) {
  if (_m.empty()) {
    return _out;
  }
  _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')';
  for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) {
    _out << ", (" << _it->first << ": " << _it->second << ')';
  }
  return _out;
}
