結果

問題 No.2410 Nine Numbers
ユーザー warabi0906
提出日時 2023-08-14 16:46:10
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 61 ms / 2,000 ms
コード長 37,788 bytes
コンパイル時間 3,042 ms
コンパイル使用メモリ 227,836 KB
実行使用メモリ 86,272 KB
最終ジャッジ日時 2024-11-22 15:46:36
合計ジャッジ時間 3,885 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'std::pair<long long int, long long int> Warabi::diameter::dfs(long long int, long long int, long long int)':
main.cpp:426:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  426 |                 auto [to,cost]=e;
      |                      ^
main.cpp:428:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  428 |                 auto [crrv,crrd]=dfs(to,v,d+1);
      |                      ^
main.cpp: In member function 'std::tuple<long long int, long long int, long long int> Warabi::diameter::get()':
main.cpp:445:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  445 |             auto [s,xxx]=dfs(0,-1,0);
      |                  ^
main.cpp:446:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  446 |             auto [t,D]=dfs(s,-1,0);
      |                  ^
main.cpp: In function 'bool Warabi::bellman_ford(const std::vector<std::tuple<long long int, long long int, long long int> >&, long long int, long long int, std::vector<long long int>&)':
main.cpp:907:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  907 |             for(auto [from,to,cost]:E){
      |                      ^

ソースコード

diff #
プレゼンテーションモードにする

/*
　Hi,I am warabi.
 Welcome to my coding space.
 Let me give you a great word of advice.
 "The pen is mightier than the sword"
            -by Edward Bulwer-Lytton
　　_,,....,,_　 ＿人人人人人人人人人人人人人人人人人人＿
-''":::::::::::::｀''＞　　　ゆっくりできるとでも?　　＜
ヽ:::::::::::::::::::::￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ￣
　|::::::;ノ´￣＼:::::::::::＼_,. -‐ｧ　　　　　＿_　　 _____　　 ＿_____
　|::::ﾉ　　　ヽ､ヽr-r'"´　　（.__　　　　,´　_,, '-´￣￣｀-ゝ 、_ イ、
_,.!イ_　　_,.ﾍｰｧ'二ﾊ二ヽ､へ,_7　　　'r ´　　　　　　　　　　ヽ、ﾝ、
::::::rｰ''7ｺ-‐'"´　 　 ;　 ',　｀ヽ/｀7　,'＝=─-　　　 　 -─=＝',　i
r-'ｧ'"´/　 /!　ﾊ 　ハ　 !　　iヾ_ﾉ　i　ｲ　iゝ、ｲ人レ／_ルヽｲ i　|
!イ´ ,' |　/__,.!/　V　､!__ﾊ　 ,'　,ゝ　ﾚﾘｲi (ﾋ_] 　　 　ﾋ_ﾝ ).| .|、i .||
`! 　!/ﾚi'　(ﾋ_] 　　 　ﾋ_ﾝ ﾚ'i　ﾉ　　　!Y!""　  ,＿__, 　 "" 「 !ﾉ i　|
,'　 ﾉ 　 !'"　   ,＿__,　 "' i .ﾚ'　　　　L.',. ヽ _ﾝ　　　　L」 ﾉ| .|
　（　　,ﾊ　　　　ヽ _ﾝ　 　人! 　　　　 | ||ヽ、　　　　　　 ,ｲ| ||ｲ| /
,.ﾍ,）､　　）＞,､ _____,　,.イ　 ハ　　　　レ ル｀ ー--─ ´ルﾚ　ﾚ´
　Take your time.
　
　GIVE ME AC!!!!!!!!!!!!!!!!!!!!!!!!!
　
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define V vector
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define brep(i,a,b) for(ll i=a;i>=b;i--)
#define reph(i,vec) for(auto &i:vec)
#define FI first
#define SE second
#define P pair
#define PB push_back
#define EB emplace_back
#define INS insert
#define all(vec) vec.begin(),vec.end()
#define in(name) ll name;cin >> name
#define ins(name) string name;cin >> name;
#define inc(name) char name;cin >> name
#define ing(name,size,E) vector<vector<ll>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);name[b].PB(a);}
#define ing_on(name,size,E) vector<vector<long long>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);}
#define ing_cost(name,size,E) vector<vector<P<ll,ll>>> name(size);rep(i,0,E){in(a);in(b);in(c);a--;b--;name[a].PB({b,c});name[b].PB({a,c});}
#define invll(name,size) vector<ll> name(size);reph(i,name)cin >> i
#define invvll(name,size1,size2) vector<vector<long long>> name(size1,vector<long long>(size2));reph(v,name)reph(i,v)cin>>i;
#define invp(name,size) vector<P<ll,ll>> name(size);for(ll i=0;i<size;i++)cin >> name[i].FI >> name[i].SE
#define out(n) cout << (n) << endl
#define _out(n) cout << " " << (n) << endl;
#define notout(n) cout << (n)
#define out_(n) cout << (n) << " "
#define set_out(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_notout(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_out_(n,k) cout << fixed << setprecision(k) << (n) << " ";
#define vout(vec) for(int i=0;i<vec.size();i++)cout<<(i?" ":"")<<(vec[i]);cout<<endl;
#define nel cout<<endl;
#define getbit(n,k) (((1LL<<(k))&(n))>0)
#define g_t(t,a) get<a>(t)
#define INF 1000000000000000000ll
#define MOD 1000000007
#define MOD2 998244353
#define CMOD MOD2
#define EPS 0.00000001
//debug
#define bug assert(false);
#define debug cout<<"OK Line "<<__LINE__<<endl;
//
//constexpr long double PI=3.14159265358979323846;
//template
template<typename T>
inline bool chmax(T& a, const T b) { if (a < b) { a = b; return true; }return false; }
template<typename T>
inline bool chmin(T& a, const T b) { if (a > b) { a = b; return true; }return false; }
//
namespace Warabi {
    //常備変数のコーナー
    V<bool> primes(1e7+5, true);
    V<ll> prime_list;
    V<ll> prime_rui(1e7+5, 0LL);
    V<bool> visiteded(300100);
    V<bool> afed(300100, false);
    V<ll> k1(200100, 0ll);
    V<ll> k2(200100, 0ll);
    //
    //常備構造体宣言のコーナー
    class UnionFind {
    private:
        ll NumberOfElements;
        ll Not1NumberOfelements;
    public:
        vector<ll> par;
        vector<ll> SIZE;
        void init(ll sz) {
            par.resize(sz, -1LL);
            SIZE.resize(sz, 1LL);
            NumberOfElements = sz;
            Not1NumberOfelements = 0ll;
        }
        ll root(ll pos) {
            if (par[pos] == -1) return pos;
            par[pos] = root(par[pos]);
            return par[pos];
        }
        bool same(ll u, ll v) {
            if (root(u) == root(v)) return true;
            return false;
        }
        ll SZ(ll u) {
            return SIZE[root(u)];
        }
        ll noe() {
            return NumberOfElements;
        }
        ll nnoe() {
            return Not1NumberOfelements;
        }
        bool unite(ll u, ll v) {
            //頂点番号が大きいほうに統合する
            u = root(u); v = root(v);
            if (u == v) {
                return false;
            }
            if (SZ(u) == 1LL and SZ(v) == 1LL)Not1NumberOfelements++;
            if (u > v)swap(u, v);
            par[u] = v;
            SIZE[v] += SIZE[u];
            NumberOfElements--;
            return true;
        }
    };
    class SCC {
    public:
        V<V<ll>> G;
        V<V<ll>> UG;
        V<ll> order;
        V<ll> GROUP;
        V<bool> visited;
        ll sz_count;
        V<ll> groupsize;
        void init(ll sz) {
            G.resize(sz, V<ll>(0));
            UG.resize(sz, V<ll>(0));
            GROUP.resize(sz, -1ll);
            visited.resize(sz, false);
            sz_count = 0LL;
            return;
        }
        void dfs(ll now) {
            visited[now] = true;
            reph(i, G[now]) {
                if (visited[i])continue;
                dfs(i);
            }
            order.PB(now);
            return;
        }
        void dfs2(ll now, ll group) {
            GROUP[now] = group;
            sz_count++;
            reph(i, UG[now]) {
                if (GROUP[i] != -1ll and GROUP[i] != group)continue;
                if (GROUP[i] != -1ll)continue;
                dfs2(i, group);
            }
            return;
        }
        void make_group(V<V<ll>> Graph_function) {
            G = Graph_function;
            rep(i, 0, (ll)G.size()) {
                reph(j, G[i]) {
                    UG[j].PB(i);
                }
            }
            rep(i, 0, (ll)G.size()) {
                if (visited[i])continue;
                dfs(i);
            }
            reverse(all(order));
            ll now_group = 0LL;
            reph(i, order) {
                if (GROUP[i] != -1)continue;
                ll prev = sz_count;
                dfs2(i, now_group);
                now_group++;
                groupsize.PB(sz_count - prev);
            }
            return;
        }
    };
    template<typename X, typename M>
    class SegmentTree {
    public:
        long long sz;
        using FX = function<X(X, X)>;
        using FA = function<X(X, M)>;
        using FM = function<M(M, M)>;
        const FX fx;
        const FA fa;
        const FM fm;
        const X ex;
        const M em;
        vector<X> node;
        vector<M> lazy;
        SegmentTree(long long sz_, FX fx_, FA fa_, FM fm_, X ex_, M em_) :sz(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_) {
            long long n = 1LL;
            while (n < sz_)n *= 2;
            sz = n;
            node.resize(sz * 2 - 1, ex);
            lazy.resize(sz * 2 - 1, em);
        }
        void set(long long index, X x) {
            node[index + sz - 1] = x;
            return;
        }
        void build() {
            for (int i = sz - 2; i >= 0; i--)node[i] = fx(node[i * 2 + 1], node[i * 2 + 2]);
            return;
        }
        void eval(long long k) {
            if (lazy[k] == em)return;
            if (k < sz - 1) {
                lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
                lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
            }
            node[k] = fa(node[k], lazy[k]);
            lazy[k] = em;
        }
        void update_sub(long long a, long long b, M x, long long k, long long l, long long r) {
            //cout << " " << a << " " << b << " " << l << " " << r << endl;
            eval(k);
            if (a <= l and r <= b) {
                lazy[k] = fm(lazy[k], x);
                //cout<<" "<<lazy[k]<<endl;
                eval(k);
                return;
            }
            else if (a < r and l < b) {
                update_sub(a, b, x, k * 2 + 1, l, (l + r) / 2);
                update_sub(a, b, x, k * 2 + 2, (l + r) / 2, r);
                node[k] = fx(node[k * 2 + 1], node[k * 2 + 2]);
                return;
            }
            return;
        }
        void update(long long a, long long b, M x) {
            update_sub(a, b, x, 0LL, 0LL, sz);
            return;
        }
        void add_sub(long long a, X x, long long k, long long l, long long r) {
            eval(k);
            node[k] += x;
            if (k < sz - 1) {
                long long mid = (l + r) / 2;
                if (a < mid)add_sub(a, x, k * 2 + 1, l, mid);
                else add_sub(a, x, k * 2 + 2, mid, r);
            }
            return;
        }
        void add(long long a, X x) {
            add_sub(a, x, 0LL, 0LL, sz);
        }
        X query_sub(long long a, long long b, long long k, long long l, long long r) {
            eval(k);
            if (r <= a or b <= l)return ex;
            else if (a <= l and r <= b)return node[k];
            else {
                X Xl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
                X Xr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
                //cout<<" / "<<Xl<<" "<<Xr<<endl;
                return fx(Xl, Xr);
            }
        }
        X query(long long a, long long b) {
            return query_sub(a, b, 0LL, 0LL, sz);
        }
        inline X operator [] (long long index) {
            return query(index, index + 1);
        }
    };
    template<typename T>
    class multimap {
    private:
        map<T, ll> mp;
    public:
        void add(ll x) {
            mp[x]++;
            return;
        }
        void del(ll x) {
            mp[x]--;
            if (mp[x] < 1)mp.erase(x);
            return;
        }
        T maximum() {
            return mp.rbegin()->first;
        }
        T minimum() {
            return mp.begin()->first;
        }
    };
    class LCA {
    public:
        vector<vector<long long>> parent;
        vector<long long> dist;
        vector<vector<long long>> G;
        LCA(const vector<vector<long long>>& gr) { init(gr); }
        void dfs(long long v, long long p, long long d) {
            parent[0][v] = p;
            dist[v] = d;
            for (long long next : G[v]) {
                if (next == p)continue;
                dfs(next, v, d + 1);
            }
            return;
        }
        void init(const vector<vector<long long>>& gr) {
            G = gr;
            parent.assign(33, vector<long long>(G.size(), -1LL));
            dist.assign(G.size(), -1LL);
            dfs(0LL, -1LL, 0LL);
            for (int i = 0; i < 32; i++) {
                for (int j = 0; j < (int)G.size(); j++) {
                    if (parent[i][j] < 0LL) {
                        parent[i + 1][j] = -1LL;
                    }
                    else {
                        parent[i + 1][j] = parent[i][parent[i][j]];
                    }
                }
            }
            return;
        }
        long long lca(long long u, long long v) {
            if (dist[u] < dist[v])swap(u, v);
            long long between = dist[u] - dist[v];
            for (int i = 0; i < 33; i++) {
                if (between & (1LL << i)) { u = parent[i][u]; }
            }
            if (u == v)return u;
            for (int i = 32; i >= 0; i--) {
                if (parent[i][u] != parent[i][v]) {
                    u = parent[i][u];
                    v = parent[i][v];
                }
            }
            assert(parent[0][u] == parent[0][v]);
            return parent[0][u];
        }
        long long get_dist(long long u, long long v) {
            return dist[u] + dist[v] - 2 * dist[lca(u, v)];
        }
        bool on_path(long long u, long long v, long long a) {
            return get_dist(u, v) == get_dist(u, a) + get_dist(v, a);
        }
    };
    class nCk {
    public:
        const long long m;
        const long long MAXIMUM = 2000005;
        vector<long long> fac, facinv, inv;
        nCk(long long m_);
        ~nCk();
        long long com(long long n, long long k)const;
    };
    nCk::nCk(long long m_) :m(m_) {
        fac.resize(MAXIMUM + 3);
        facinv.resize(MAXIMUM + 3);
        inv.resize(MAXIMUM + 3);
        fac[0] = fac[1] = 1;
        facinv[0] = facinv[1] = 1;
        inv[1] = 1;
        for (long long i = 2; i < MAXIMUM + 2; i++) {
            fac[i] = fac[i - 1] * i % m;
            inv[i] = m - inv[m % i] * (m / i) % m;
            facinv[i] = facinv[i - 1] * inv[i] % m;
        }
    }
    nCk::~nCk() {}
    long long nCk::com(long long n, long long k)const {
        if (k == 0)return 1;
        assert(!(n < 0 || k < 0));
        return fac[n] * (facinv[k] * facinv[n - k] % m) % m;
    }
    //
    //常備構造体宣言のコーナー
    
    //
    //常備関数のコーナー
    void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
    void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
    //木の直径を求める
    class diameter{
        private:
        long long N;
        vector<vector<pair<long long,long long>>> G;
        pair<long long,long long> dfs(long long v,long long p,long long d){
            long long Max_v=v,Max_dist=d;
            for(const pair<long long,long long> &e:G[v]){
                auto [to,cost]=e;
                if(to==p)continue;
                auto [crrv,crrd]=dfs(to,v,d+1);
                if(Max_dist<crrd){
                    Max_dist=crrd;
                    Max_v=crrv;
                }
            }
            return make_pair(Max_v,Max_dist);
        }
        public:
        diameter(long long n_):N(n_){
            G.resize(N);
        }
        void Add_edge(long long u,long long v,long long c=1){
            G[u].emplace_back(v,c);G[v].emplace_back(u,c);
            return;
        }
        tuple<long long,long long,long long> get(){
            auto [s,xxx]=dfs(0,-1,0);
            auto [t,D]=dfs(s,-1,0);
            return make_tuple(s,t,D);
        }
    };
    //素数の取得
    void prime_init(const long long Limit) {
        V<bool> at(Limit, true);
        primes = at;
        primes[0] = primes[1] = false;
        rep(i, 2, Limit) {
            if (!primes[i])continue;
            for (ll j = i * 2; j <= Limit; j += i)primes[j] = false;
        }
        rep(i, 1, Limit) {
            if (primes[i]) {
                prime_list.PB(i);
                prime_rui[i] = prime_rui[i - 1] + 1;
            }
            else {
                prime_rui[i] = prime_rui[i - 1];
            }
        }
        return;
    }
    //modpow
    long long modpow(long long a, long long b, long long m) {
        long long p = 1, q = a;
        for (int i = 0; i < 63; i++) {
            if ((b & (1LL << i)) != 0) {
                p *= q;
                p %= m;
            }
            q *= q;
            q %= m;
        }
        return p;
    }
    //逆元
    long long Div(long long a, long long b, long long m) {
        return (a * modpow(b, m - 2, m)) % m;
    }
    //点と点の距離を返す
    long double Dis(ll ax, ll ay, ll bx, ll by) {
        return sqrt(pow(ax - bx, 2) + pow(ay - by, 2));
    }
    //二つのベクトルから平行四辺形の面積を返す
    ll he(ll x0, ll y0, ll x1, ll y1, ll x2, ll y2) {//外積を二で割る
        return abs((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0));
    }
    //
    template<typename T>
    ll Lis_size(V<T> arr, ll sz) {
        const T TINF = numeric_limits<T>::max();
        V<T> DP(sz + 1, TINF);
        DP[0] = -TINF;
        rep(i, 0, sz) {
            *lower_bound(all(DP), arr[i]) = arr[i];
        }
        ll ans = 0LL;
        rep(i, 1, sz + 1) {
            if (DP[i] != TINF)ans = i;
        }
        return ans;
    }
    string toBinary(ll n) {
        string r;
        while (n != 0LL) {
            r += (n % 2LL == 0LL ? "0" : "1");
            n /= 2LL;
        }
        return r;
    }
    template<typename T>
    V<ll> press(V<T> arr) {
        V<T> X = arr;
        sort(all(X));
        X.erase(unique(all(X)), X.end());
        V<ll> ans(arr.size());
        rep(i, 0LL, (ll)arr.size()) {
            ans[i] = lower_bound(all(X), arr[i]) - X.begin();
        }
        return ans;
    }
    P<V<V<ll>>, V<V<P<ll, ll>>>> warshall_floyd(ll N, V<V<P<ll, ll>>> G) {
        V<V<ll>> DP(N, V<ll>(N, INF));
        rep(i, 0, N)DP[i][i] = 0LL;
        V<V<P<ll, ll>>> prev(N, V<P<ll, ll>>(N, { INF,INF }));
        rep(i, 0, N) {
            reph(j, G[i]) {
                DP[i][j.FI] = j.SE;
                prev[i][j.FI] = { i,j.FI };
            }
        }
        rep(k, 0, N) {
            rep(i, 0, N) {
                rep(j, 0, N) {
                    if (chmin(DP[i][j], DP[i][k] + DP[k][j])) {
                        prev[i][j] = prev[k][j];
                    }
                }
            }
        }
        return { DP,prev };
    }
    template<typename T>
    void to_sum(V<T>& arr) {
        rep(i, 0, (ll)arr.size() - 1LL) {
            arr[i + 1] += arr[i];
        }
        return;
    }
    template<typename T>
    void including_map(ll H, ll W, V<V<T>>& G, T c) {
        V<V<T>> new_G(H + 2, V<T>(W + 2));
        rep(i, 0, W + 2)new_G[0][i] = c;
        rep(i, 1, H + 1) {
            new_G[i][0] = c;
            new_G[i][W + 1] = c;
            rep(j, 1, W + 1) {
                new_G[i][j] = G[i - 1][j - 1];
            }
        }
        rep(i, 0, W + 2)new_G[H + 1][i] = c;
        G = new_G;
        return;
    }
    
template<typename T> class BIT {
private:
    int n;
    vector<T> bit;
public:
    // 0_indexed で i 番目の要素に x を加える
    void add(int i, T x){
        i++;
        while(i < n){
            bit[i] += x, i += i & -i;
        }
    }
    // 0_indexed で [0,i] の要素の和(両閉区間！！)
    T sum(int i){
        i++;
        T s = 0;
        while(i > 0){
            s += bit[i], i -= i & -i;
        }
        return s;
    }
    BIT(){}
    //初期値がすべて0の場合
    BIT(int sz) : n(sz+1), bit(n, 0){}
    BIT(const vector<T>& v) : n((int)v.size()+1), bit(n, 0){
        for(int i = 0; i < n-1; i++){
            add(i,v[i]);
        }
    }
    void print(){
        for(int i = 0; i < n-1; i++){
            cout << sum(i) - sum(i-1) << " ";
        }
        cout << "\n";
    }
    //-1スタート
    void print_sum(){
        for(int i = 0; i < n; i++){
            cout << sum(i-1) << " ";
        }
        cout << "\n";
    }
};
 
// u を昇順にソートするのに必要な交換回数(転倒数) (u は {0,..., n-1} からなる重複を許した長さ n の数列)
long long inv_count(const vector<long long>& u,const int Max)
{
    int n=u.size();
    int m=Max;
    BIT<long long> bt(m);
    long long ans = 0;
    for(int i = 0; i < n; i++){
        ans += i - bt.sum(u[i]);
        bt.add(u[i], 1);
    }
    return ans;
}
    set<ll> factor(ll N) {
        set<ll> ans;
        for (ll i = 1LL; i * i <= N; i++) {
            if (N % i)continue;
            ans.INS(i);
            ans.INS(N / i);
        }
        return ans;
    }
    V<ll> dijkstra(ll sz, V<V<P<ll, ll>>> G, ll s) {
        V<ll> ans(sz, INF); ans[s] = 0LL;
        priority_queue<P<ll, ll>, vector<P<ll, ll>>, greater<P<ll, ll>>> examine;
        examine.push({ 0LL,s });
        while (examine.size()) {
            P<ll, ll> p = examine.top();
            examine.pop();
            ll now = p.SE, dist = p.FI;
            if (ans[now] < dist)continue;
            reph(i, G[now]) {
                ll next = i.FI, c = i.SE;
                if (chmin(ans[next], dist + c)) {
                    examine.push({ dist + c,next });
                }
            }
        }
        return ans;
    }
    V<ll> pass(const V<V<ll>>& G, ll s, ll t) {
        V<ll> ans, res;
        function<void(ll,ll)> dfs = [&](ll now,ll p) {
            res.PB(now);
            if (now == t) {
                ans = res;
            }
            reph(next, G[now]) {
                if (next==p)continue;
                dfs(next,now);
            }
            res.pop_back();
            return;
        };
        dfs(s,-1);
        return ans;
    }
    // 負の数にも対応した mod (a = -11 とかでも OK)
    inline long long mod(long long a, long long m) {
        long long res = a % m;
        if (res < 0) res += m;
        return res;
    }
    // 拡張 Euclid の互除法
    long long extGCD(long long a, long long b, long long& p, long long& q) {
        if (b == 0) { p = 1; q = 0; return a; }
        long long d = extGCD(b, a % b, q, p);
        q -= a / b * p;
        return d;
    }
    long long extGcd(long long a, long long b, long long& p, long long& q) {
        if (b == 0) { p = 1; q = 0; return a; }
        long long d = extGcd(b, a % b, q, p);
        q -= a / b * p;
        return d;
    }
    // 逆元計算 (ここでは a と m が互いに素であることが必要)
    long long modinv(long long a, long long m) {
        long long x, y;
        extGCD(a, m, x, y);
        return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
    }
    // Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない)
    // for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])"
    //      coeffs[k] = m[0]m[1]...m[k-1]
    //      constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2]
    long long Garner(vector<long long> b, vector<long long> m, long long Mmod) {
        m.push_back(Mmod); // banpei
        vector<long long> coeffs((int)m.size(), 1);
        vector<long long> constants((int)m.size(), 0);
        for (int k = 0; k < (int)b.size(); ++k) {
            long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]);
            for (int i = k + 1; i < (int)m.size(); ++i) {
                (constants[i] += t * coeffs[i]) %= m[i];
                (coeffs[i] *= m[k]) %= m[i];
            }
        }
        return constants.back();
    }
    pair<long long, long long> ChineseRem(const vector<long long>& b, const vector<long long>& m) {
        long long r = 0, M = 1;
        for (int i = 0; i < (int)b.size(); ++i) {
            long long p, q;
            long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
            if ((b[i] - r) % d != 0) return make_pair(0, -1);
            long long tmp = (b[i] - r) / d * p % (m[i] / d);
            r += M * tmp;
            M *= m[i] / d;
        }
        return make_pair(mod(r, M), M);
    }
    map<ll, ll> bunkai(ll n) {
        map<ll, ll> ans;
        ll Nn = n;
        for (int i = 2; i * i <= Nn; i++) {
            while (n % i == 0) {
                n /= i;
                ans[i]++;
            }
        }
        if (n > 1) { ans[n]++; }
        return ans;
    }
    template<typename T>
    void RLE(vector<T>& arr) {
        vector<T> res;
        res.push_back(arr[0]);
        for (const T t : arr) {
            if (res.back() != t)res.push_back(t);
        }
        arr = res;
        return;
    }
    vector<pair<long long, long long>> EulerTour(const vector<vector<long long>>& G) {
        long long N = (long long)G.size();
        vector<pair<long long, long long>> res(N);
        long long now = 0ll;
        function<void(long long, long long)> dfs = [&](long long v, long long p) {
            res[v].first = now;
            ++now;
            for (const long long next : G[v]) {
                if (next == p)continue;
                dfs(next, v);
            }
            res[v].second = now;
            ++now;
            return;
        };
        dfs(0, -1ll);
        return res;
    }
    
    template <typename T>
    struct BIT2D {
        int H, W;
        vector<vector<T>> bit;  // データの格納先
        BIT2D(int H_, int W_) { init(H_, W_); }
        void init(int H_, int W_) {
            H = H_ + 1;
            W = W_ + 1;
            bit.assign(H, vector<T>(W, 0));
        }
        void add(int h, int w, T x) {
            for (int i = h; i < H; i += (i & -i)) {
                for (int j = w; j < W; j += (j & -j)) {
                    bit[i][j] += x;
                }
            }
        }
        // 1≦i≦h かつ 1≦j≦w
        T sum(int h, int w) {
            T s(0);
            for (int i = h; i > 0; i -= (i & -i)) {
                for (int j = w; j > 0; j -= (j & -j)) {
                    s += bit[i][j];
                }
            }
            return s;
        }
        // h1≦i<h2 かつ w1≦j<w2
        T query(int h1, int w1, int h2, int w2) {
            return sum(h2 - 1, w2 - 1) - sum(h2 - 1, w1 - 1) - sum(h1 - 1, w2 - 1) + sum(h1 - 1, w1 - 1);
        }
    };
    
    template<typename T>
    struct Matrix {
      vector<vector<T>>A;
      Matrix() {}
      Matrix(size_t n,size_t m):A(n,vector<T>(m,0)){}
      Matrix(size_t n):A(n,vector<T>(n,0)){};
      size_t height(){
        return (A.size());
      }
      size_t width(){
        return (A[0].size());
      }
      inline const vector<T>&operator[](int k)const{
        return (A.at(k));
      }
      inline vector<T>&operator[](int k){
        return (A.at(k));
      }
      static Matrix E(size_t n){
        Matrix mat(n);
        for(int i=0;i<n;i++)mat[i][i]=1;
        return (mat);
      }
      Matrix &operator+=(Matrix&B){
        size_t n=height(),m=width();
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]+=B[i][j];
        return (*this);
      }
      Matrix &operator-=(Matrix&B){
        size_t n=height(),m=width();
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)(*this)[i][j]-=B[i][j];
        return (*this);
      } 
    Matrix &operator*=(Matrix&B) {
        size_t n=height(),m=B.width(),p=width();
        vector<vector<T>> C(n,vector<T>(m,0));
        for(int i=0;i<n;i++)for(int j=0;j<m;j++)for(int k=0;k<p;k++)C[i][j]+=(*this)[i][k]*B[k][j];
        A.swap(C);
        return (*this);
     }
    Matrix &operator^=(long long k){
            Matrix B=Matrix::E(height());
        while(k>0){
          if(k&1)B*=*this;
          *this*=*this;
          k>>=1LL;
        }
        A.swap(B.A);
        return (*this);
      }
      Matrix operator+(Matrix&B){
        return (Matrix(*this)+=B);
      }
      Matrix operator-(Matrix &B){
        return (Matrix(*this)-=B);
      }
      Matrix operator*(Matrix&B){
        return (Matrix(*this)*=B);
      }
      Matrix operator^(long long k){
        return (Matrix(*this)^=k);
      }
    };
    
    long long BGstep(long long a,long long b,long long p){
        //solve a^x≡b(mod p) O(√p)
        long long m=ceil(sqrt(p));
        map<long long,long long> power;
        for(int i=m-1;0<=i;i--){
            power[modpow(a,i,p)]=i;
        }
        long long c=Div(1ll,modpow(a,m,p),p);
        for(int i=0;i<m;i++){
            long long d=(b*modpow(c,i,p))%p;
            if(power.count(d))return i*m+power[d];
        }
        return -1;
    }
    bool bellman_ford(const vector<tuple<long long,long long,long long>> &E,long long N,long long S,vector<long long> &dist){
        const long long inf=1e9;
        dist.resize(N,inf);
        dist[S]=0ll;
        for(int i=0;i<N;i++){
            bool end=true;
            for(auto [from,to,cost]:E){
                if(dist[from]==inf)continue;
                if(dist[from]+cost<dist[to]){
                    dist[to]=dist[from]+cost;
                    end=false;
                }
            }
            if(end)return false;
        }
        return true;
    }
    class TopologicalSort{
        private:
        int N;
        vector<vector<int>> G;
        public:
        TopologicalSort(const vector<vector<int>> &g):G(g){};
        vector<int> order;
        bool sort(function<bool(int,int)> compare=[](int a,int b){return a<b;}){
            N=G.size();
            priority_queue<int,vector<int>,function<bool(int,int)>> pq(compare);
            vector<int> in_edge(N,0);
            for(int i=0;i<N;i++){
                for(const int &nxt:G[i]){
                    in_edge[nxt]++;
                }
            }
            for(int i=0;i<N;i++)if(!in_edge[i])pq.push(i);
            while(pq.size()){
                int v=pq.top();pq.pop();
                order.push_back(v);
                for(const int &nxt:G[v]){
                    if(--in_edge[nxt])continue;
                    pq.push(nxt);
                }
            }
            return N==(ll)order.size();
        }
    };
    class Doubling{
        private:
        const vector<int> G;
        const int Max;
        vector<vector<int>> doubling;
        public:
        Doubling(const vector<int> g,int m):G(g),Max(m){
            //2^Max-1
            int N=G.size();
            doubling.resize(N);
            for(int i=0;i<N;i++)doubling[i].resize(Max,-1);
            for(int i=0;i<N;i++)doubling[i][0]=G[i];
            for(int i=0;i<Max-1;i++){
                for(int j=0;j<N;j++)doubling[j][i+1]=doubling[doubling[j][i]][i];
            }
            return;
        };
        int get(int v,long long K){
            int ans=v;
            for(int i=0;i<Max;i++){
                if(K&(1ll<<i))ans=doubling[ans][i];
            }
            return ans;
        }
    };
//from https://algo-logic.info/tree-dp/#
struct Rerooting {
    /* start 問題ごとに書き換え */
    struct DP {  // DP の型
        long long black,white;// 全部black/一つでもwhiteを含む
        DP(long long b,long long w) : black(b),white(w) {}
    };
    const DP identity = DP(0,-1e9);  // 単位元(末端の値は add_root(identity) になるので注意)
    function<DP(DP, DP)> merge = [](DP dp_cum, DP d) -> DP {
        return DP(dp_cum.black+d.black,max(dp_cum.white+max(d.black,d.white),dp_cum.black+d.white));
    };
    function<DP(DP)> add_root = [](DP d) -> DP {
        return DP(d.white+1,max(d.white,d.black));
    };
    /* end 問題ごとに書き換え */
    // グラフの定義
    struct Edge {
        int to;
    };
    using Graph = vector<vector<Edge>>;
    vector<vector<DP>> dp;  // dp[v][i]: vから出るi番目の有向辺に対応する部分木のDP
    vector<DP> ans;         // ans[v]: 頂点vを根とする木の答え
    Graph G;
    Rerooting(int N) : G(N) {
        dp.resize(N);
        ans.assign(N, identity);
    }
    void add_edge(int a, int b) {
        G[a].push_back({b});
    }
    void build() {
        dfs(0);            // 普通に木DP
        bfs(0, identity);  // 残りの部分木に対応するDPを計算
    }
    DP dfs(int v, int p = -1) {  // 頂点v, 親p
        DP dp_cum = identity;
        int deg = G[v].size();
        dp[v] = vector<DP>(deg, identity);
        for (int i = 0; i < deg; i++) {
            int u = G[v][i].to;
            if (u == p) continue;
            dp[v][i] = dfs(u, v);
            dp_cum = merge(dp_cum, dp[v][i]);
        }
        //DP dp_=add_root(dp_cum);
        //printf("%d\n",v);
        //printf("{%lld,%lld}\n",dp_.black,dp_.white);
        return add_root(dp_cum);
    }
    void bfs(int v, const DP& dp_p, int p = -1) {  // bfs だが、実装が楽なので中身は dfs になっている
        int deg = G[v].size();
        for (int i = 0; i < deg; i++) {  // 前のbfsで計算した有向辺に対応する部分木のDPを保存
            if (G[v][i].to == p) dp[v][i] = dp_p;
        }
        vector<DP> dp_l(deg + 1, identity), dp_r(deg + 1, identity);  // 累積merge
        for (int i = 0; i < deg; i++) {
            dp_l[i + 1] = merge(dp_l[i], dp[v][i]);
        }
        for (int i = deg - 1; i >= 0; i--) {
            dp_r[i] = merge(dp_r[i + 1], dp[v][i]);
        }
        ans[v] = add_root(dp_l[deg]);  // 頂点 v の答え
        for (int i = 0; i < deg; i++) {  // 一つ隣の頂点に対しても同様に計算
            int u = G[v][i].to;
            if (u == p) continue;
            bfs(u, add_root(merge(dp_l[i], dp_r[i + 1])), v);
        }
    }
};
}
namespace Guest {
    const int MAX_VAL = 300000;
    int a[MAX_VAL]; //要素
    int cnt[MAX_VAL]; //区間内のiの個数
    int res;        //区間内の種類の数
    class Mo {
    private:
        vector<int> left, right;
        const int width;
        void add(const int id);
        void del(const int id);
    public:
        vector<int> ans;
        Mo(const int n) : width((int)sqrt(n)) {}
        //クエリ[l,r)
        void insert(const int l, const int r) {
            left.push_back(l), right.push_back(r);
        }
        void solve() {
            const int sz = (int)left.size();
            int nl = 0, nr = 0;
            vector<int> ord(sz);
            iota(ord.begin(), ord.end(), 0);
            sort(ord.begin(), ord.end(), [&](const int a, const int b) {
                const int c = left[a] / width, d = left[b] / width;
            return (c == d) ? ((c & 1) ? (right[b] < right[a]) : (right[a] < right[b])) : (c < d);
                });
            ans.resize(sz);
            for (const int id : ord) {
                while (nl > left[id]) add(--nl);
                while (nr < right[id]) add(nr++);
                while (nl < left[id]) del(nl++);
                while (nr > right[id]) del(--nr);
                ans[id] = res;
            }
        }
    };
    //idは元の配列のインデックス
    void Mo::add(const int id)
    {
        res -= cnt[a[id]] / 2;
        res += (++cnt[a[id]]) / 2;
    }
    void Mo::del(const int id)
    {
        res -= cnt[a[id]] / 2;
        res += (--cnt[a[id]]) / 2;
    }
    
constexpr long long mod=MOD2;
class mint {
long long x;
public:
    mint(long long x=0) : x((x%mod+mod)%mod) {}
    mint operator-() const { 
      return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += mod-a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= mod;
        return *this;
    }
    bool operator==(const mint a){
        return x==a.x;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const {
        return pow(mod-2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }           
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};
struct RollingHash {
    static const int base1 = 1007, base2 = 2009;
    static const int mod1 = 1000000007, mod2 = 1000000009;
    vector<long long> hash1, hash2, power1, power2;
    // construct
    RollingHash(const vector<long long> &S) {
        int n = (int)S.size();
        hash1.assign(n+1, 0);
        hash2.assign(n+1, 0);
        power1.assign(n+1, 1);
        power2.assign(n+1, 1);
        for (int i = 0; i < n; ++i) {
            hash1[i+1] = (hash1[i] * base1 + S[i]) % mod1;
            hash2[i+1] = (hash2[i] * base2 + S[i]) % mod2;
            power1[i+1] = (power1[i] * base1) % mod1;
            power2[i+1] = (power2[i] * base2) % mod2;
        }
    }
    
    // get hash of S[left:right]
    inline pair<long long, long long> get(int l, int r) const {
        long long res1 = hash1[r] - hash1[l] * power1[r-l] % mod1;
        if (res1 < 0) res1 += mod1;
        long long res2 = hash2[r] - hash2[l] * power2[r-l] % mod2;
        if (res2 < 0) res2 += mod2;
        return {res1, res2};
    }
    // get lcp of S[a:] and S[b:]
    inline int getLCP(int a, int b) const {
        int len = min((int)hash1.size()-a, (int)hash1.size()-b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a+mid) != get(b, b+mid)) high = mid;
            else low = mid;
        }
        return low;
    }
    // get lcp of S[a:] and T[b:]
    inline int getLCP(const RollingHash &T, int a, int b) const {
        int len = min((int)hash1.size()-a, (int)hash1.size()-b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a+mid) != T.get(b, b+mid)) high = mid;
            else low = mid;
        }
        return low;
    }
};
}
//
long long gcd(long long a, long long b) {
    if (b == 0LL)return a;
    return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}
signed main() {
    /*
    文章を読み落としていませんか?
    制約も隅々まで読んでいますか?
    注意
    ・セグ木のupdate関数はl,rの値を渡したときにl以上r未満の区間だからご注意を
    　rは含みません
    ・BITって1-indexedなんだぜ
    　イケてるよな
    ・using namespace Warabi??
    */
    //using namespace Warabi;
    //mintのMODは確認した?
    rep(i,0,9)out_(pow(3,i));nel;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0