#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ALL(a) (a).begin(),(a.end())
#define brep(n,hhh) for(int i=n-1;i>=hhh;i--)
#define rep(hhh,n)   for(int i=hhh;i<n;i++)
#define jrep(hhh,n) for(int j=hhh;j<n;j++)
#define krep(hhh,n) for(int k=hhh;k<n;k++)
#define lrep(hhh,n) for(int l=hhh;l<n;l++)
#define rrep(i,k,n) for(int i=k;i<n;i++)
#define out(n)   cout << n <<endl;
#define sot(A) sort(A.begin(),A.end())
#define rsot(A) sort(A.rbegin(),A.rend())
#define vi vector<int>
#define vb vector<bool>
#define vd vector<double>
#define vld vector<long double>
#define vpd vector<pair<double,double>>
#define vc vector<char>
#define vs vector<string>
#define vpi vector<pair<int,int>>
#define vvc vector<vector<char>>
#define vvi vector<vector<int>>
#define vvd vector<vector<double>>
#define vvpd vector<vector<pair<double,double>>>
#define vvb vector<vector<bool>>
#define vvvi vector<vector<vector<int>>>
#define vvvvi vector<vector<vector<vector<int>>>>
#define vvvpi vector<vector<vector<Pi>>>
#define vvpi vector<vector<pair<int,int>>>
#define vvtpi vector<vector<tuple<int,int,int>>>
#define dout(x,y) cout<<x<<" "<<y<<endl;
#define tout(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl;
#define Pi pair<int,int>
#define Pd pair<double,double>
#define Pdi pair<double,int>
#define TPi tuple<int,int,int>
#define QPi tuple<int,int,int,int>
#define FPi tuple<int,int,int,int,int>
#define TPd tuple<double,int,int>
#define spi pair<string,int>
#define pb push_back
constexpr int MOD1=1000000007;
constexpr int MOD2=998244353;
constexpr int BIG=10000000000000000;
//int BBB=ppow(2,31)-1;
class BIT {
public:
    //データの長さ
    int n;
    //データの格納先
    vector<int> a;
    //コンストラクタ
    BIT(int n):n(n),a(n+1,0){}

    //a[i]にxを加算する
    void add(int i,int x){
        i++;
        if(i==0) return;
        for(int k=i;k<=n;k+=(k & -k)){
            a[k]+=x;
            //a[k]%=MOD2;
        }
    }
    void conf(){
        for(int i=0;i<=n;i++){
            cout<<a[i]<<' ';
        }
        cout<<endl;
    }

    //a[i]+a[i+1]+…+a[j]を求める
    int sum(int i,int j){
        return (sum(j)-sum(i-1));
    }

    //a[0]+a[1]+…+a[i]を求める
    int sum(int i){
        i++;
        int s=0;
        if(i==0) return s;
        for(int k=i;k>0;k-=(k & -k)){
            s+=a[k];
            //s%=MOD2;
        }
        return s;
    }

    //a[0]+a[1]+…+a[i]>=xとなる最小のiを求める(任意のkでa[k]>=0が必要)
    int lower_bound(int x){
        if(x<=0){
            //xが0以下の場合は該当するものなし→0を返す
            return 0;
        }else{
            int i=0;int r=1;
            //最大としてありうる区間の長さを取得する
            //n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while(r<n) r=r<<1;
            //区間の長さは調べるごとに半分になる
            for(int len=r;len>0;len=len>>1) {
                //その区間を採用する場合
                if(i+len<n && a[i+len]<x){
                    x-=a[i+len];
                    i+=len;
                }
            }
            return i;
        }
    }
};
class CR{
public:
 
    vi fac;
    vi finv;
    vi inv;
    int MOD;
    CR(int N,int M):fac(N+1),finv(N+1),inv(N+1){
        MOD=M;
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i <= N; 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;
        }
    }
 
// 二項係数計算
    long long COM(int n, int k){
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }
};//MODには素数
namespace internal {

template <class T> struct simple_queue {
    std::vector<T> payload;
    int pos = 0;
    void reserve(int n) { payload.reserve(n); }
    int size() const { return (int)(payload.size()) - pos; }
    bool empty() const { return pos == (int)(payload.size()); }
    void push(const T& t) { payload.push_back(t); }
    T& front() { return payload[pos]; }
    void clear() {
        payload.clear();
        pos = 0;
    }
    void pop() { pos++; }
};

}
template <class Cap> struct mf_graph {
  public:
    mf_graph() : _n(0) {}
    mf_graph(int n) : _n(n), g(n) {}

    int add_edge(int from, int to, Cap cap) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        assert(0 <= cap);
        int m = (int)(pos.size());
        pos.push_back({from, (int)(g[from].size())});
        int from_id = (int)(g[from].size());
        int to_id = (int)(g[to].size());
        if (from == to) to_id++;
        g[from].push_back(_edge{to, to_id, cap});
        g[to].push_back(_edge{from, from_id, 0});
        return m;
    }

    struct edge {
        int from, to;
        Cap cap, flow;
    };

    edge get_edge(int i) {
        int m = (int)(pos.size());
        assert(0 <= i && i < m);
        auto _e = g[pos[i].first][pos[i].second];
        auto _re = g[_e.to][_e.rev];
        return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};
    }
    std::vector<edge> edges() {
        int m = (int)(pos.size());
        std::vector<edge> result;
        for (int i = 0; i < m; i++) {
            result.push_back(get_edge(i));
        }
        return result;
    }
    void change_edge(int i, Cap new_cap, Cap new_flow) {
        int m = (int)(pos.size());
        assert(0 <= i && i < m);
        assert(0 <= new_flow && new_flow <= new_cap);
        auto& _e = g[pos[i].first][pos[i].second];
        auto& _re = g[_e.to][_e.rev];
        _e.cap = new_cap - new_flow;
        _re.cap = new_flow;
    }

    Cap flow(int s, int t) {
        return flow(s, t, std::numeric_limits<Cap>::max());
    }
    Cap flow(int s, int t, Cap flow_limit) {
        assert(0 <= s && s < _n);
        assert(0 <= t && t < _n);
        assert(s != t);

        std::vector<int> level(_n), iter(_n);
        internal::simple_queue<int> que;

        auto bfs = [&]() {
            std::fill(level.begin(), level.end(), -1);
            level[s] = 0;
            que.clear();
            que.push(s);
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (auto e : g[v]) {
                    if (e.cap == 0 || level[e.to] >= 0) continue;
                    level[e.to] = level[v] + 1;
                    if (e.to == t) return;
                    que.push(e.to);
                }
            }
        };
        auto dfs = [&](auto self, int v, Cap up) {
            if (v == s) return up;
            Cap res = 0;
            int level_v = level[v];
            for (int& i = iter[v]; i < (int)(g[v].size()); i++) {
                _edge& e = g[v][i];
                if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;
                Cap d =
                    self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));
                if (d <= 0) continue;
                g[v][i].cap += d;
                g[e.to][e.rev].cap -= d;
                res += d;
                if (res == up) break;
            }
            return res;
        };

        Cap flow = 0;
        while (flow < flow_limit) {
            bfs();
            if (level[t] == -1) break;
            std::fill(iter.begin(), iter.end(), 0);
            while (flow < flow_limit) {
                Cap f = dfs(dfs, t, flow_limit - flow);
                if (!f) break;
                flow += f;
            }
        }
        return flow;
    }

    std::vector<bool> min_cut(int s) {
        std::vector<bool> visited(_n);
        internal::simple_queue<int> que;
        que.push(s);
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            visited[p] = true;
            for (auto e : g[p]) {
                if (e.cap && !visited[e.to]) {
                    visited[e.to] = true;
                    que.push(e.to);
                }
            }
        }
        return visited;
    }

  private:
    int _n;
    struct _edge {
        int to, rev;
        Cap cap;
    };
    std::vector<std::pair<int, int>> pos;
    std::vector<std::vector<_edge>> g;
};
int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (unsigned int)(n)) x++;
    return x;
}
template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {
  public:
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& v) : _n((int)v.size()) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push(r >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};
namespace internal {

template <class E> struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    csr(int n, const std::vector<std::pair<int, E>>& edges)
        : start(n + 1), elist(edges.size()) {
        for (auto e : edges) {
            start[e.first + 1]++;
        }
        for (int i = 1; i <= n; i++) {
            start[i] += start[i - 1];
        }
        auto counter = start;
        for (auto e : edges) {
            elist[counter[e.first]++] = e.second;
        }
    }
};


struct scc_graph {
  public:
    scc_graph(int n) : _n(n) {}

    int num_vertices() { return _n; }

    void add_edge(int from, int to) { edges.push_back({from, {to}}); }

    // @return pair of (# of scc, scc id)
    std::pair<int, std::vector<int>> scc_ids() {
        auto g = csr<edge>(_n, edges);
        int now_ord = 0, group_num = 0;
        std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
        visited.reserve(_n);
        auto dfs = [&](auto self, int v) -> void {
            low[v] = ord[v] = now_ord++;
            visited.push_back(v);
            for (int i = g.start[v]; i < g.start[v + 1]; i++) {
                auto to = g.elist[i].to;
                if (ord[to] == -1) {
                    self(self, to);
                    low[v] = std::min(low[v], low[to]);
                } else {
                    low[v] = std::min(low[v], ord[to]);
                }
            }
            if (low[v] == ord[v]) {
                while (true) {
                    int u = visited.back();
                    visited.pop_back();
                    ord[u] = _n;
                    ids[u] = group_num;
                    if (u == v) break;
                }
                group_num++;
            }
        };
        for (int i = 0; i < _n; i++) {
            if (ord[i] == -1) dfs(dfs, i);
        }
        for (auto& x : ids) {
            x = group_num - 1 - x;
        }
        return {group_num, ids};
    }

    std::vector<std::vector<int>> scc() {
        auto ids = scc_ids();
        int group_num = ids.first;
        std::vector<int> counts(group_num);
        for (auto x : ids.second) counts[x]++;
        std::vector<std::vector<int>> groups(ids.first);
        for (int i = 0; i < group_num; i++) {
            groups[i].reserve(counts[i]);
        }
        for (int i = 0; i < _n; i++) {
            groups[ids.second[i]].push_back(i);
        }
        return groups;
    }

  private:
    int _n;
    struct edge {
        int to;
    };
    std::vector<std::pair<int, edge>> edges;
};

} 
struct scc_graph {
  public:
    scc_graph() : internal(0) {}
    scc_graph(int n) : internal(n) {}

    void add_edge(int from, int to) {
        int n = internal.num_vertices();
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        internal.add_edge(from, to);
    }

    std::vector<std::vector<int>> scc() { return internal.scc(); }

  private:
    internal::scc_graph internal;
};
void conf(vs &A){
    for(string i:A){
        cout<<i<<' ';
    }
    cout<<endl;
}
void conf(vd &A){
    for(double i:A){
        cout<<i<<' ';
    }
    cout<<endl;
}
void conf(vi &A){
    for(int i:A){
        cout<<i<<' ';
    }
    cout<<endl;
}
void conf(vvvi &A,int k){
    rep(0,A.size()){
        jrep(0,A[i].size()){
            cout<<A[i][j][k]<<' ';
        }
        cout<<endl;
    }
}
void conf(set<int> &S){
    for(int i:S)cout<<i<<' ';
    cout<<endl;
}
void conf(vc &A){
    for(char i:A){
        cout<<i;
    }
    cout<<endl;
}
void conf(vb &A){
    for(auto i:A){
        cout<<i<<' ';
    }
    cout<<endl;
}
void conf(vvi &A){
    rep(0,A.size()){
        jrep(0,A[i].size()){
            cout<<A[i][j]<<" ";
        }
        cout<<endl;
    }
}
void conf(vvd &A){
    rep(0,A.size()){
        jrep(0,A[i].size()){
            cout<<A[i][j]<<" ";
        }
        cout<<endl;
    }
}
void conf(vvc &A){
    rep(0,A.size()){
        jrep(0,A[i].size()){
            cout<<A[i][j];
        }
        cout<<endl;
    }
}
void conf(vvb &A){
    rep(0,A.size()){
        jrep(0,A[i].size()){
            cout<<(int)A[i][j]<<" ";
        }
        cout<<endl;
    }
}
void conf(vvpi &A){
    rep(0,A.size()){
        jrep(0,A[i].size()){
            cout<<"("<<A[i][j].first<<" "<<A[i][j].second<<")"<<" ";
        }
        cout<<endl;
    }
}
void conf(vpi &A){
    rep(0,A.size()){
        cout <<'('<< A[i].first <<" "<<A[i].second<<')'<<" ";
    }
    cout<<endl;
}
int max(int a,int b){
    if(a>b)return a;
    else return b;
}
int min(int a,int b){
    if(a>b)return b;
    else return a;
}

int modpow(int x,int n,int mod){
    int res=1;
    while(n>0){
        int l=x%mod;
        if(n&1)res=(res%mod)*l%mod;
        x=l*l%mod;
        n>>=1;
    }
    return res;
}//高速べき乗(modの値を返す)、計算量log(N)
int ppow(int x,int n){
    int res=1;
    while(n>0){
        if(n&1)res=res*x;
        x=x*x;
        n>>=1;
    }
    return res;
}//高速べき乗、計算量log(N)
int modinv(int a, int m) {
    int b = m, u = 1, v = 0;
    while (b) {
        int t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}//拡張EuClidの互除法、逆元を返す,a,mが互いに素ならOK、mがＭＯＤ，log(a);
vi smallest_prime_factors(int n) {
    vi spf(n + 1);
    for (int i = 0; i <= n; i++) spf[i] = i;


    for (int i = 2; i * i <= n; i++) {
        if (spf[i] == i) {
            for (int j = i * i; j <= n; j += i) {
                if (spf[j] == j) {
                    spf[j] = i;
                }
            }
        }
    }

    return spf;
}
vector<int> enumdiv(int n) { 
    vector<int> S;
    for (int i = 1; 1LL*i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); }
    sort(S.begin(), S.end());
    return S;
}//与えられた１つの数の約数をvectorで昇順で返す（重複なし）,計算量√N

vi soinsu(int N){
    vi T;
    int n=N;
    int k=2;
    while(k*k<=n){
        if(N%k==0){
            N=N/k;
            T.push_back(k);
        }
        else{
            k++;
        }
    }
    if(N!=1)T.push_back(N);
    if(T.size()==0){
        T.push_back(n);
    }
    return T;
}//素因数分解した結果をviで返す(sort済み),O(√N)
int legendre(int N,int k){
    int ans=0;
    int K=k;
    while(N>=K){
        ans+=N/K;
        K*=k;
    }
    return ans;
}//N!がkで何回割ることが出来るか

vb Eratosthenes(int N){
    vb IsPrime(N+1,true);
    IsPrime[0] = false; // 0は素数ではない
    IsPrime[1] = false; // 1は素数ではない

    for(int i=2; i*i<=N; ++i) // 0からsqrt(max)まで調べる
        if(IsPrime[i]) // iが素数ならば
            for(int j=2; i*j<=N; ++j) // (max以下の)iの倍数は
                IsPrime[i*j] = false;
    return IsPrime;
}//Nまでの数が素数か素数でないかを返す、計算量nloglogn


int lgcd(int A, int B){
    //int a,b,C;
    while (A!=0 && B!=0){
        if (A>B){
            //a=A/B;
            A-=A/B*B;
        }else{ 
            //b=B/A;
            B-=B/A*A;
        }
        //out(7)
    }
    //C=max(A,B);
    return max(A,B);
}
int lcm(int a, int b) {
    return a / lgcd(a, b) * b;
}
void YN(bool A){
    if(A){
        out("Yes");
    }else{
        out("No");
    }
}
double max(double a,double b){
    if(a>b){
        return a;
    }else{
        return b;
    }
}
double min(double a,double b){
    if(a>b){
        return b;
    }else{
        return a;
    }
}

vvi mat_mul(vvi &a, vvi &b,int MOD) {
  vvi res(a.size(), vi(b[0].size(),0));
  for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < b[0].size(); j++) {
      for (int k = 0; k < b.size(); k++) {
        (res[i][j] ^= a[i][k]&b[k][j]);
      }
    }
  }
  return res;
}

vvi mat_pow(vvi a, int n,int MOD) {
    int d=1;
  vvi res(a.size(), vi(a.size()));
  // 単位行列で初期化
  
  for (int i = 0; i < a.size(); i++)
    res[i][i] = (d<<33)-1;
  // 繰り返し二乗法
  while (n > 0) {
    if (n & 1) res = mat_mul(a, res,MOD);
    a = mat_mul(a, a,MOD);
    n >>= 1;
  }
  return res;
}


template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n((v.size())) {
        log = ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};


struct dsu {
  public:
    dsu() : _n(0) {}
    dsu(int n) : _n(n), parent_or_size(n, -1) {}

    int merge(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        int x = leader(a), y = leader(b);
        if (x == y) return x;
        if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
        parent_or_size[x] += parent_or_size[y];
        parent_or_size[y] = x;
        return x;
    }

    bool same(int a, int b) {
        assert(0 <= a && a < _n);
        assert(0 <= b && b < _n);
        return leader(a) == leader(b);
    }

    int leader(int a) {
        assert(0 <= a && a < _n);
        if (parent_or_size[a] < 0) return a;
        return parent_or_size[a] = leader(parent_or_size[a]);
    }

    int size(int a) {
        assert(0 <= a && a < _n);
        return -parent_or_size[leader(a)];
    }

    std::vector<std::vector<int>> groups() {
        std::vector<int> leader_buf(_n), group_size(_n);
        for (int i = 0; i < _n; i++) {
            leader_buf[i] = leader(i);
            group_size[leader_buf[i]]++;
        }
        std::vector<std::vector<int>> result(_n);
        for (int i = 0; i < _n; i++) {
            result[i].reserve(group_size[i]);
        }
        for (int i = 0; i < _n; i++) {
            result[leader_buf[i]].push_back(i);
        }
        result.erase(
            std::remove_if(result.begin(), result.end(),
                           [&](const std::vector<int>& v) { return v.empty(); }),
            result.end());
        return result;
    }

  private:
    int _n;
    // root node: -1 * component size
    // otherwise: parent
    std::vector<int> parent_or_size;
};

//NODESの大きさは((N+Q)logN)
//Tはセグ木に載せる型、Fはラムダ式で演算を記述
//Nはとりあえず大きい数字を設定しておけばOK
template <typename T, typename F, int NODES = 300000>
struct PersistentSegmentTree {
  using ll = long long;
  struct Node {
    T data;
    Node *l, *r;
    Node() {}
    Node(const T &_data) : data(_data), l(nullptr), r(nullptr) {}
  };

  Node *pool;
  int pid;
  ll N;
  const F f;
  const T ID;
  Node *nil;
  vector<Node *> roots;

  PersistentSegmentTree(const vector<T> &v, const F &f_, const T &ID_)
      : pid(0), f(f_), ID(ID_), nil(nullptr) {
    pool = new Node[NODES];
    nil = my_new(ID);
    nil->l = nil->r = nil;
    roots.reserve(262144);
    roots.push_back(build(v));
  }

  PersistentSegmentTree(const ll &N_, const F &f_, const T &ID_)
      : pid(0), N(N_), f(f_), ID(ID_), nil(nullptr) {
    pool = new Node[NODES];
    nil = my_new(ID);
    nil->l = nil->r = nil;
    roots.reserve(262144);
    roots.push_back(nil);
  }

  Node *my_new(const T &data) {
    pool[pid].data = data;
    pool[pid].l = pool[pid].r = nil;
    return &(pool[pid++]);
  }

  Node *merge(Node *l, Node *r) {
    pool[pid].data = f(l->data, r->data);
    pool[pid].l = l;
    pool[pid].r = r;
    return &(pool[pid++]);
  }

  Node *build(const vector<T> &v) {
    N = (ll)v.size();
    return build(0, (ll)v.size(), v);
  }

  Node *build(ll l, ll r, const vector<T> &v) {
    if (l + 1 == r) return my_new(v[l]);
    ll m = (l + r) >> 1;
    return merge(build(l, m, v), build(m, r, v));
  }

 private:
  Node *update_(ll a, const T &x, Node *n, ll l, ll r) {
    if (l + 1 == r) return my_new(x);
    ll m = (l + r) >> 1;
    if (a < m) return merge(update_(a, x, n->l, l, m), n->r);
    return merge(n->l, update_(a, x, n->r, m, r));
  }
  Node *add_(ll a, const T &x, Node *n, ll l, ll r) {
    if (l + 1 == r) return my_new(f(x, n->data));
    ll m = (l + r) >> 1;
    if (a < m) return merge(add_(a, x, n->l, l, m), n->r);
    return merge(n->l, add_(a, x, n->r, m, r));
  }
  T query_(ll a, ll b, Node *n, ll l, ll r) {
    if (n == nil) return ID;
    if (r <= a or b <= l) return ID;
    if (a <= l and r <= b) return n->data;
    ll m = (l + r) >> 1;
    return f(query_(a, b, n->l, l, m), query_(a, b, n->r, m, r));
  }

 public:
  Node *update(Node *n, ll k, const T &x) {
    Node *root = update_(k, x, n, 0, N);
    roots.push_back(root);
    return root;
  }
  Node *update(int t, ll k, const T &x) {
    Node *root = update_(k, x, roots[t], 0, N);
    roots.push_back(root);
    return root;
  }
  Node *update(ll k, const T &x) {
    Node *root = update_(k, x, roots.back(), 0, N);
    roots.push_back(root);
    return root;
  }

  Node *add(Node *n, ll k, const T &x) {
    Node *root = add_(k, x, n, 0, N);
    roots.push_back(root);
    return root;
  }
  Node *add(int t, ll k, const T &x) {
    Node *root = add_(k, x, roots[t], 0, N);
    roots.push_back(root);
    return root;
  }
  Node *add(ll k, const T &x) {
    Node *root = add_(k, x, roots.back(), 0, N);
    roots.push_back(root);
    return root;
  }

  T query(Node *n, ll a, ll b) { return query_(a, b, n, 0, N); }
  T query(int t, ll a, ll b) { return query_(a, b, roots[t], 0, N); }
  T query(ll a, ll b) { return query_(a, b, roots.back(), 0, N); }

  Node *new_tree() { return nil; }
};
struct UnionFind {
    vector<int> par, rank, siz;

    // 構造体の初期化
    UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { }

    // 根を求める
    int leader(int x) {
        if (par[x]==-1) return x; // x が根の場合は x を返す
        else return par[x] = leader(par[x]); // 経路圧縮
    }

    // x と y が同じグループに属するか (= 根が一致するか)
    bool same(int x, int y) {
        return leader(x)==leader(y);
    }

    // x を含むグループと y を含むグループを併合する
    bool merge(int x, int y) {
        int rx = leader(x), ry = leader(y); // x 側と y 側の根を取得する
        if (rx==ry) return false; // すでに同じグループのときは何もしない
        // union by rank
        par[ry] = rx; // ry を rx の子とする
        siz[rx] += siz[ry]; // rx 側の siz を調整する
        return true;
    }

    // x を含む根付き木のサイズを求める
    int size(int x) {
        return siz[leader(x)];
    }
};
vi dikstra(int s,int V,vvpi &G){
    vi d(V,BIG);
    priority_queue<Pi,vector<Pi>,greater<Pi>> que;
    d[s]=0;
    que.push(Pi(0,s));//Pi(距離、向かう頂点)
    
    while(!que.empty()){
        Pi p=que.top();que.pop();
        int v=p.second;
        if(d[v]<p.first)continue;
        rep(0,G[v].size()){
            int a=G[v][i].second;
            int b=G[v][i].first;
            if(d[a]>d[v]+b){
                d[a]=d[v]+b;
                que.push(Pi(d[a],a));
            }
        }
    }
    return d;
    
}//始点は0start
int op(int a, int b) {
    return max(a,b);
}

int e() {
    return 0;
}
//int target;

//bool f(int v) { return v >= target; }
struct loopdfs{
    public:
        int flgggg;
        bool gg;
        bool x;
        int start;
loopdfs(int n){
    flgggg=-1;
    gg=false;
    x=false;
    start=n;//0-indexed
};
void loops(int a,vvi &G,vb &seen,vi &loop,vi &prev){
    seen[a]=true;
    for (auto nv : G[a]) { 
        if(gg)continue;
        if (seen[nv]){
            flgggg=nv;
            gg=true;
            x=true;
            break;
        }
        loops(nv,G,seen,loop,prev); 
    }
    if(!gg&&x){
        prev.push_back(a);
    }
    if(gg){
        loop.push_back(a);
    }
    if(flgggg==a)gg=false;
    if(a==start){
        reverse(loop.begin(),loop.end());
        reverse(prev.begin(),prev.end());
    }
}//有向なfunctional graphのみ動作確認、

};
vvi calcNext(const string &S) {
    int n = (int)S.size();
    vector<vector<int> > res(n+1, vector<int>(26, n));
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j];
        res[i][S[i]-'a'] = i;
    }
    return res;
}



struct S{
    int v;
    //int size;
};/*
S op(S a,S b){
    return {min(a.v,b.v)};
}
S e(){
    return {BIG};
}
S mapping(int a, S b){
    return {a+b.v};
}
int composition(int a,int b){
    return a+b;
}
int id(){return 0;}*/
 
 
vi compress(vi &A){
    vi vals=A;
    sot(vals);
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    vi X(A.size());
    rep(0,A.size()){
        X[i]=lower_bound(vals.begin(),vals.end(),A[i])-vals.begin();
    }
    return X;
}//0-indexed
template <typename T>
vector<T> compress(vector<T> &C1, vector<T> &C2,int w) {
    vector<T> vals;
    int N = (int)C1.size();
    for (int i = 0; i < N; i++) {
        for (int d = 0; d <= 0; d++) {  // for (T d = 0; d <= 0; d++) でも良い
            T tc1 = C1[i] - d;
            if(tc1>=0){
            vals.push_back(tc1);
            }
            T tc2 = C2[i] + d;
            if(tc2<=w){
            vals.push_back(tc2);
            }
        }
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 0; i < N; i++) {
        C1[i] = lower_bound(vals.begin(), vals.end(), C1[i]) - vals.begin();
        C2[i] = lower_bound(vals.begin(), vals.end(), C2[i]) - vals.begin();
    }
    return vals;
}//2次元座標圧縮

int kruskal(vector<TPi> &A,int V){
    rsot(A);
    int M=A.size();
    dsu uf(V);
    int res=0;
    rep(0,M){
        int a=get<1>(A[i]);int b=get<2>(A[i]); int c=get<0>(A[i]);
        if(!uf.same(a,b)){
            uf.merge(a,b);
            res+=c;
        }
    }
    bool flag=false;
    rep(0,V){
        if(!uf.same(i,0))flag=true;
    }
    if(flag){
        res=-1;
    }
    return res;
}

string encode(string& str) {
    string ret = ""; // 答えを格納
    int n=(int)(str.size());
    for (int l = 0; l < n;) {
        int r = l + 1;
        while(r < n && str[l] == str[r]){
            r++;
        }
        ret.push_back(str[l]);
        char num_str = (char)((r - l)+'0'); // 出現回数
        ret += num_str;
        l = r;
    }
    return ret;
}
bool revsort(const Pi &a,const Pi &b){
    if(a.first>b.first){
        return true;
    }else{
        if(a.first==b.first){
            if(a.second<b.second){
                return true;
            }else{
                return false;
            }
        }else{
            return false;
        }
    }
}//Piでfirst降順、second昇順
bool anglesortbool(const Pi &a,const Pi &b){
    int x=a.first*b.second-a.second*b.first;
    if(x>0){
        return true;
    }else{
        return false;
    }
}
vpi anglesort(vpi &A){
    vvpi qua(4);
    rep(0,A.size()){
        int x=A[i].first;int y=A[i].second;
        if(x>0&&y>=0){
            qua[0].push_back(Pi(x,y));
        }
        if(x<=0&&y>0){
            qua[1].push_back(Pi(x,y));
        }
        if(x<0&&y<=0){
            qua[2].push_back(Pi(x,y));
        }
        if(x>=0&&y<0){
            qua[3].push_back(Pi(x,y));
        }
    }
    rep(0,4){
        sort(qua[i].begin(),qua[i].end(),anglesortbool);
    }
    
    vpi B;
    rep(0,4){
        jrep(0,qua[i].size()){
            B.pb(qua[i][j]);
        }
    }
    return B;
}//偏角ソート、pairの値は10＾9まで、0から2Πを昇順にソート
void predfs1(vvb &G,int h,int w,int H,int W){
    if(G[h][w])return;
    G[h][w]=true;
    vi dh={1,0,-1,0};
    vi dw={0,1,0,-1};
    rep(0,4){
        int x=h+dh[i];int y=w+dw[i];
        if(x>=0&&x<=H-1&&y>=0&&y<=W-1&&(!G[x][y])){
            
            predfs1(G,x,y,H,W); // 再帰的に探索
        }
    }
   
}
void predfs(vb &seen,int a,vvi &G){
    if(seen[a])return;
    seen[a]=true;
    
    for(int i:G[a]){
        if(seen[i])continue;
        predfs(seen,i,G); // 再帰的に探索
    }
    
}
int bdp2(int N,int bit,vi &dp,vb &seen){
    if(seen[bit]){
        //out(7)
        return dp[bit];
    }
    //out(7)
    int res = dp[bit];
    brep((1<<N),0){
        i&=bit;
        int pbit=bit&(~i);
        if(i==0||pbit==0)continue;
        //dout(bit,pbit)
        res=min(bdp2(N,i,dp,seen)+bdp2(N,pbit,dp,seen),res);
    }
    seen[bit]=true;
    return dp[bit]=res; // メモしながらリターン
}

vvi prebfs1(vvc &G,vvi &A,int h,int w,int H,int W){
    vi dh={1,0,-1,0};
    vi dw={0,1,0,-1};
    A[h][w]=0;
    queue<Pi> que;
    que.push(Pi(h,w));
    while(!que.empty()){
        Pi v=que.front();que.pop();
        rep(0,4){
        int x=v.first+dh[i];int y=v.second+dw[i];
        if(x>=0&&x<=H-1&&y>=0&&y<=W-1&&(A[x][y]==-1)&&G[x][y]!='#'){
            que.push(Pi(x,y));
            A[x][y]=A[v.first][v.second]+1;
        }
        }
    }
    return A;
}
vi prebfs(vvi &G,int a,int N){
    vi dist(N, -1); // 全頂点を「未訪問」に初期化
    queue<int> que;
    dist[a] = 0;
    que.push(a); // 0 を橙色頂点にする
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; 
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }
    return dist;
}


signed main(){
    string S,T;cin>>S>>T;
    int N;cin>>N;
    rep(0,N){
        S+='_';
        S+=T;
    }
    out(S)
    
    
    
}