#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair P; typedef pair PL; const ll mod = 1000000007; const ll MOD = 1000000007; const ll INF = 1LL << 60; #define PI (acos(-1)) #define ALL(c) (c).begin(), (c).end() template istream &operator>>(istream &is, vector &vec) { for (auto &v : vec) is >> v; return is; } template ostream &operator<<(ostream &os, const vector &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const deque &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const pair &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; // template template inline string toString(const T &a) { ostringstream oss; oss << a; return oss.str(); }; template struct ModInt { int x; ModInt() : x(0) {} ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} ModInt &operator+=(const ModInt &p) { if ((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if ((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while (b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ret(1), mul(x); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt(t); return (is); } static int get_mod() { return mod; } }; using modint = ModInt; template struct Combination { vector _fact, _rfact, _inv; Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) { _fact[0] = _rfact[sz] = _inv[0] = 1; for (int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i; _rfact[sz] /= _fact[sz]; for (int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1); for (int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1]; } inline T fact(int k) const { return _fact[k]; } inline T rfact(int k) const { return _rfact[k]; } inline T inv(int k) const { return _inv[k]; } T P(int n, int r) const { if (r < 0 || n < r) return 0; return fact(n) * rfact(n - r); } T C(int p, int q) const { if (q < 0 || p < q) return 0; return fact(p) * rfact(q) * rfact(p - q); } T H(int n, int r) const { if (n < 0 || r < 0) return (0); return r == 0 ? 1 : C(n + r - 1, r); } T NC(int p, int q) const { modint ret = 1; for (int i = 1; i <= q; i += 1) { ret = ret * p / i; p--; } return ret; } }; ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; } bool is_prime(ll x) { if (x == 1) { return false; } for (ll i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; } map prime_factor(int64_t n) { map ret; for (int64_t i = 2; i * i <= n; i++) { while (n % i == 0) { ret[i]++; n /= i; } } if (n != 1) ret[n] = 1; return ret; } vector divisor(ll n) { vector ret; for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } } sort(begin(ret), end(ret)); return (ret); } long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } long long modinv(long long a, long long mod) { return modpow(a, mod - 2, mod); } const ll MAX = 510000; ll fac[MAX], finv[MAX], inv[MAX]; void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (ll i = 2; i < MAX; i++) { fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } ll COM(ll n, ll k) { if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } struct UnionFind { vector par; UnionFind(int n) : par(n, -1) {} void init(int n) { par.assign(n, -1); } int root(int x) { if (par[x] < 0) return x; else return par[x] = root(par[x]); } bool issame(int x, int y) { return root(x) == root(y); } bool merge(int x, int y) { x = root(x); y = root(y); if (x == y) return false; if (par[x] > par[y]) swap(x, y); // merge technique par[x] += par[y]; par[y] = x; return true; } int size(int x) { return -par[root(x)]; } }; struct BIT { //1-indexed!!! int n; vector bit; BIT() { init(); } BIT(int n) : n(n) { init(); } void init() { bit.clear(); bit.resize(n + 1, 0); } int sum(int i) { int s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } int sum(int x, int y) { return sum(y) - sum(x - 1); } void add(int i, int x) { while (i <= n) { bit[i] += x; i += i & -i; } } int lower_bound(int w) { if (w <= 0) return 0; int x = 0, r = 1; while (r < n) r <<= 1; for (int k = r; k > 0; k >>= 1) { if (x + k <= n && bit[x + k] < w) { w -= bit[x + k]; x += k; } } return x + 1; } }; struct LazySegmentTree { // private: ll n; vector node, lazy; // public: LazySegmentTree(vector v) { int sz = (int)v.size(); n = 1; while (n < sz) n *= 2; node.resize(2 * n - 1); lazy.resize(2 * n - 1, 0); for (int i = 0; i < sz; i++) node[i + n - 1] = v[i]; for (int i = n - 2; i >= 0; i--) node[i] = node[i * 2 + 1] + node[i * 2 + 2]; } void eval(int k, int l, int r) { if (lazy[k] != 0) { node[k] += lazy[k]; if (r - l > 1) { lazy[2 * k + 1] += lazy[k] / 2; lazy[2 * k + 2] += lazy[k] / 2; } lazy[k] = 0; } } void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; eval(k, l, r); if (b <= l || r <= a) return; if (a <= l && r <= b) { lazy[k] += (r - l) * x; eval(k, l, r); } else { add(a, b, x, 2 * k + 1, l, (l + r) / 2); add(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = node[2 * k + 1] + node[2 * k + 2]; } } ll getsum(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; eval(k, l, r); if (b <= l || r <= a) return 0; if (a <= l && r <= b) return node[k]; ll vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r); return vl + vr; } }; ll digit_sum(ll v) { ll ret = 0; while (v) { ret += (v % 10); v /= 10; } return ret; } template struct Kruskal { struct edge { ll from, to; T cost; ll used; edge() {} edge(ll from, ll to, T cost) : from(from), to(to), cost(cost), used(0) {} bool operator<(const edge &e) const { return cost < e.cost; } }; ll n; vector p, r; vector edges; Kruskal() {} Kruskal(ll n) : n(n) {} void init(ll n) { r.assign(n, 1); p.resize(n); iota(p.begin(), p.end(), 0); } ll find(ll x) { return (x == p[x] ? x : p[x] = find(p[x])); } bool same(ll x, ll y) { return find(x) == find(y); } void unite(ll x, ll y) { x = find(x); y = find(y); if (x == y) return; if (r[x] < r[y]) swap(x, y); r[x] += r[y]; p[y] = x; } void add_edge(ll u, ll v, T c) { edges.emplace_back(u, v, c); } T build() { sort(edges.begin(), edges.end()); init(n); T res = 0; for (auto &e : edges) { if (!same(e.from, e.to)) { res += e.cost; unite(e.from, e.to); e.used = 1; } } return res; } T build(ll k) { sort(edges.begin(), edges.end()); init(n); T res = 0; ll cnt = 0; for (auto &e : edges) { if (!same(e.from, e.to)) { res += e.cost; unite(e.from, e.to); e.used = 1; cnt++; } if (cnt == k) { break; } } return res; } }; int LIS(int a[], int n) { vector A(n, 0x3f3f3f3f); for (int i = 0; i < n; i++) *lower_bound(A.begin(), A.end(), a[i]) = a[i]; return find(A.begin(), A.end(), 0x3f3f3f3f) - A.begin(); } // string maze[1010]; ll maze[100][100]; ll grid_bfs(ll H, ll W, ll sx, ll sy, ll gx, ll gy) { int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; vector> dist(H, vector(W, -1)); dist[sy][sx] = 0; queue q; q.push({sy, sx}); while (!q.empty()) { ll x, y; tie(y, x) = q.front(); q.pop(); if (y == gy && x == gx) { break; } for (int t = 0; t < 4; t++) { ll nx = x + dx[t], ny = y + dy[t]; if (nx < 0 || ny < 0 || nx >= W || ny >= H || dist[ny][nx] != -1 || maze[ny][nx] == '#') { continue; } dist[ny][nx] = dist[y][x] + 1; q.push({ny, nx}); } } return dist[gy][gx]; } // no verify ll bfs(ll n, ll start, vector> Edges) { vector dist(n + 1, -1); dist[start] = 0; queue q; q.push({start, 0}); while (!q.empty()) { ll node, cost; tie(cost, node) = q.front(); q.pop(); for (auto p : Edges[node]) { ll v = p.first, cost = p.second; if (dist[v] == -1) { dist[v] = dist[node] + cost; q.push({v, cost}); } } } } vector> warshall_floyd(ll n, vector> g, ll INF) { //init vector> c(10,vector(10,0)); for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (g[i][k] == INF || g[k][j] == INF) continue; g[i][j] = min(g[i][j], g[i][k] + g[k][j]); } } } return g; } struct Dijkstra { ll n; vector>> Edges; vector Dist; vector Prev; vector PathNum; Dijkstra(ll n) : n(n), Edges(n), Dist(n), Prev(n), PathNum(n) { Prev.assign(n, -1); }; void add_edge(ll a, ll b, ll c, bool directed = true) { if (directed) { Edges[a].emplace_back(make_pair(b, c)); } else { Edges[a].emplace_back(make_pair(b, c)); Edges[b].emplace_back(make_pair(a, c)); } } // O((E+V)logV) void build(int start) { priority_queue, greater

> queue; fill(Dist.begin(), Dist.end(), 1e+18); //1e18 !?!? fill(Prev.begin(), Prev.end(), -1); //1e18 !?!? Dist[start] = 0; PathNum[start] = 1; queue.push(PL(0, start)); while (!queue.empty()) { PL p = queue.top(); queue.pop(); int v = p.second; if (Dist[v] < p.first) continue; for (int i = 0; i < Edges[v].size(); i++) { PL e = Edges[v][i]; if (Dist[e.first] > Dist[v] + e.second) { Dist[e.first] = Dist[v] + e.second; queue.push(P(Dist[e.first], e.first)); Prev[e.first] = v; PathNum[e.first] = PathNum[v]; } else if (Dist[e.first] == Dist[v] + e.second) { PathNum[e.first] += PathNum[v]; PathNum[e.first] %= MOD; } } } } ll dist(ll t) { return Dist[t]; } vector get_path(ll t) { vector path; for (; t != -1; t = Prev[t]) { path.push_back(t); } reverse(path.begin(), path.end()); return path; } ll get_path_num(ll t) { return PathNum[t]; } // int solve() // { // ll v, e, r; // cin >> v >> e >> r; // Dijkstra dij(v); // for (int i = 0; i < e; i++) // { // ll a, b, c; // cin >> a >> b >> c; // dij.add_edge(a, b, c); // } // dij.build(r); // for (int i = 0; i < v; i++) // { // if (dij.dist(i) == 1e18) // { // cout << "INF" << endl; // } // else // { // cout << dij.dist(i) << endl; // cout << dij.get_path(i) << endl; // cout << dij.get_path_num(i) << endl; // } // } // return 0; // } }; struct CumulativeSum2D { int H; int W; vector> data; CumulativeSum2D(int H, int W) : H(H), W(W), data(H + 1, vector(W + 1, 0LL)) {} void add(int x, int y, ll z) { data[x + 1][y + 1] += z; } void build() { for (int i = 1; i < data.size(); i++) { for (int j = 1; j < data[i].size(); j++) { data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1]; } } } void print() { for (int i = 0; i <= H; i++) { for (int j = 0; j <= W; j++) { cout << data[i][j] << " "; } cout << endl; } } ll query(int sx, int sy, int gx, int gy) { return (data[gy][gx] - data[sy - 1][gx] - data[gy][sx - 1] + data[sy - 1][sx - 1]); } }; struct LCA { int n, h; vector> par; vector>> v; vector depth, dis; LCA(int sz) : n(sz), v(n), depth(n), dis(n) { h = 1; while ((1 << h) < n) h++; par.assign(h, vector(n, -1)); } void add_edge(int x, int y, int z) { v[x].push_back({y, z}); v[y].push_back({x, z}); } void dfs(int x, int p, int d, ll di) { par[0][x] = p; depth[x] = d; dis[x] = di; for (auto to : v[x]) if (to.first != p) dfs(to.first, x, d + 1, di + to.second); } void build() { dfs(0, -1, 0, 0); for (int i = 0; i < h - 1; i++) { for (int j = 0; j < n; j++) { if (par[i][j] < 0) par[i + 1][j] = -1; else par[i + 1][j] = par[i][par[i][j]]; } } } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int i = 0; i < h; i++) if ((depth[v] - depth[u]) >> i & 1) v = par[i][v]; if (u == v) return u; for (int i = h - 1; i >= 0; i--) { if (par[i][u] != par[i][v]) { u = par[i][u]; v = par[i][v]; } } return par[0][u]; } ll dist(int u, int v) { return dis[u] + dis[v] - 2 * dis[lca(u, v)]; } // int solve() // { // ll n; // cin >> n; // LCA lca(n); // for (int i = 0; i < n - 1; i++) // { // ll u, v, w; // cin >> u >> v >> w; // lca.add_edge(u, v, w); // } // lca.build(); // ll q; // cin >> q; // while (q--) // { // ll a, b, c; // cin >> a >> b >> c; // cout << (lca.dist(a, b) + lca.dist(b, c) + lca.dist(c, a)) / 2 << endl; // } // return 0; // } }; vector compress(vector r) { //1-indexed set se; for (int i = 0; i < r.size(); i++) { se.insert(r[i]); } map m; ll cnt = 1; for (auto t : se) { m[t] = cnt; cnt++; } for (int i = 0; i < r.size(); i++) { r[i] = m[r[i]]; } return r; } void YES() { cout << "YES" << endl; exit(0); } void NO() { cout << "NO" << endl; exit(0); } void Yes() { cout << "Yes" << endl; exit(0); } void No() { cout << "No" << endl; exit(0); } void m1() { cout << -1 << endl; exit(0); } template void out(const T t) { cout << t << '\n'; } template void fout(const T t) { cout << fixed << setprecision(10) << t << '\n'; } /*------------------------------*/ void solve() { ll n; cin >> n; vector two,five,ans; ll a = 1, b = 1; for(int i=0; i <= n; i++){ two.push_back(a); a *= 2; } for (int i = 0; i <= n; i++) { five.push_back(b); b *= 5; } for(int i=0; i <= n; i++){ for(int j=0; j <= n; j++){ ans.push_back(two[i] * five[j]); } } sort(ALL(ans)); for(int i=0; i < ans.size(); i++){ out(ans[i]); } } int main() { cout.precision(10); ios::sync_with_stdio(false); cin.tie(0); solve(); return 0; } //IMOS //https://imoz.jp/algorithms/imos_method.html /*名前 accumulate(ALL(b),0LL) prev_permutation(ALL(v)) 辞書順で一個前の順列を構築する bitcount __builtin_popcountll 二次元累積和 CumulativeSum2D 10進数の桁和 digit_sum (b*b+c*c)**0.5 hypot cout << fixed << setprecision(10) << ans << endl; // 文字列t ->整数 atoi(t.c_str()); // 文字列t ->long long整数 stoll(t); ローカルではつかえない */ /*実装例 ********** DP ********** ・ナップサックDP https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_C 個数制限なしナップサック N<=100,W<=10000,v<=1000 https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_B 01ナップサック N<=100,W<=10000,v<=1000 https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_F 01ナップサック N<=100,W<=10^9,v<=100 https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/1/DPL_1_H 巨大ナップザック N=40 w<10^15 , v<10^15 解)半分全列挙して、wi > wj かつvi < vj となるようなiを除いて、二分探索 ・部分文字列DP https://qiita.com/drken/items/a207e5ae3ea2cf17f4bd next[i][c] := S の i 文字目以降で最初に文字 c が登場する index https://www.hackerrank.com/contests/bbc003/challenges/bbc003-e/submissions/code/1321355726 (部分文字列の中で+の個数の偶奇によって、カウントするか決める) No.852 連続部分文字列 https://yukicoder.me/problems/no/852/editorial 連続な部分文字列における、文字の種類数の平均を求める 解)右端を固定すると dp[i+1] = dp[i] + (左にs[i]がでてきた位置との距離) ・桁DP 1 https://atcoder.jp/contests/abc029/tasks/abc029_d n以下の数字の中で現れた1の数を求める dp[i][j][k]:i桁目まで見たときに1の個数がk個の数字の個数 S - Digit Sum https://atcoder.jp/contests/dp/tasks/dp_s n以下の数字の中で、各桁の総和がDの倍数となるものを数える E - Almost Everywhere Zero https://atcoder.jp/contests/abc154/tasks/abc154_e n以下の数字の中で,0でない数字が丁度K個あるものの数を数える ************* 組み合わせ ************* https://codeforces.com/contest/888/problem/D 少なくともn-k個がpi=iとなるような順列の組の数え上げ →pi≠iとなる順列をモンモール数という。n-k~n個をpi=iと固定したときに、他の要素がpi≠iとなるような組み合わせの数(モンモール数)の積をとる https://codeforces.com/problemset/problem/322/B 赤・青・緑の花束が存在し、ある色を3本or全ての色を1本ずつ使ったときに、できる花束の最大数 https://atcoder.jp/contests/abc021/tasks/abc021_d https://codeforces.com/problemset/problem/1288/C 1 <=a1 <= a2 <= ... <= ak <= n となる(a1,a2..ak)の組の数 →等号がなければ単純にn個の要素の中からk個を選べばよい -> C(n,k) →等号がある場合は重複を許してk個選べばよい      -> H(n,k) ************* 最短経路 ************* https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_e 移動できるノード数に制限がある場合の最短経路問題 →事前に幅優先探索でノード毎に移動できるノードを求めて、ダイクストラ ************* 遅延セグ木 ************* https://atcoder.jp/contests/abc153/submissions/10165699 *********** BIT *********** https://atcoder.jp/contests/abc157/tasks/abc157_e(アルファベット毎にBITもつやつ) https://hoj.hamako-ths.ed.jp/onlinejudge/problems/1276(中央値求めるやつ) */