a way to РЭ 0 баллов

struct sgt{
    vector<ll> t;
    int d;
    void merge(int i){
        t[i] = t[2*i+1] + t[2*i];
    }
    sgt(vector<ll> a){
        int k = 1;
        int n = sz(a);
        while(k<= n){
            k*=2;
        }
        t.resize(2*k);
        d = k;
        loop(i, d, d+n){
            t[i] = a[i-d];
        }
        for(int i = d-1; i >0; i--){
            merge(i);
        }
    }
    ll query(int l, int r, int ls, int rs, int v){
        if(ls > r || rs < l){
            return 0;
        }
        if(ls >= l && rs <= r){
//            cout << ls << " " << rs << " " << l << " " << r << " " << v << endl;
            return t[v];
        }
        int m = (ls+rs)/2;
        return query(l, r, ls, m, 2*v) + query(l, r, m+1, rs, 2*v+1);
    }


    ll query(int l, int r){
        return query(l, r, 0, d-1, 1);
    }

    void upd(int l, int r, int i, int x, int v){
        if(l == r){
            t[v] = x;
            return;
        }
        int m = (l+r)/2;
        if(i <= m){
            upd(l, m, i, x, 2*v);
        }else{
            upd(m+1, r, i, x, 2*v + 1);
        }
        merge(v);
    }
    void upd(int i, int x){
        upd(0, d-1, i, x, 1);
    }
};
void segment() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    loop(i, 0, n) cin >> a[i];
    sgt s(a);
    loop(i, 0, m){
        int type;
        cin >> type;
        if(type == 1){
            int dd1, x;
            cin >> dd1 >> x;
            s.upd(dd1, x);
        }else{
            int l, r;
            cin >> l >> r;
            r-=1;
            cout << s.query(l, r) << '\n';
        }
    }
}

int fastpow(int a, int n, int prime){
    // a^n = a
    if(n == 1){
        return a;
    }
    if(n%2 == 0){
        int x = fastpow(a, n/2, prime);
        return (x*x) % prime;
    }
    return (fastpow(a, n-1, prime) * a) % prime;
}
int fastpow_binary(int a, int n, int prime){
    int res = 1;
    while(n){
        if(n&1) res = res*a % prime;
        a = a*a % prime;
        n>>=1;
    }
    return res;

}
vector<int> fact;
int rev(int a, int p){
    int ans = fastpow_binary(a, p-2, p);
    return ans;
}

int cnk(int n, int k, int p){
    return fact[n] * rev(fact[k], p ) % p * rev(fact[n-k], p) % p;
}
void solve_cnk(){
    int n, k , p = 13;
    cin >> n >> k;
    fact.resize(n+1);
    fact[1] = 1;
    loop(i, 2, n+1){
        fact[i] = fact[i-1] * i % p;
    }
    cout << cnk(n, k, p);
}


struct bridges{
    vector<vector<int>> g;
    vector<int> used;
    vector<int> h, d;

    void dfs(int v, int p = -1){
        used[v] = 1;
        d[v] = h[v] = (p == -1 ? 0 : h[p]+1);
        for(auto to : g[v]){
            if(p != to){
                if(used[to]){
                    d[v] = min(d[v], h[to]);
                }else{
                    dfs(to, v);
                    d[v] = min(d[v], d[to]);
                    if(h[v] < d[to]){
                        // мост
                    }
                }
            }
        }
    }

    bridges(int n, int m){
        g.resize(n);
        used.resize(n);
        h.resize(n); // прямые ребра
        d.resize(n); // обратные ребра
        loop(i, 0, m){
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb(b);
            g[b].pb(a);
        }


    }
};

struct topsort{
    vector<vector<int>> g;
    vector<int> used;
    vector<int> tp;
    void dfs(int v, int p = -1){
        used[v] = 1;
        for(auto to : g[v]){
            if(!used[to]){
                dfs(to);
            }
        }
        tp.pb(v);
    }

    topsort(int n, int m){
        g.resize(n);
        used.resize(n);
        loop(i, 0, m){
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb(b);
//            g[b].pb(a);
        }
        loop(i, 0, n){
            if(!used[i]){
                dfs(i);
            }
        }
        reverse(all(tp));
        for(auto i : tp){
            cout << i << " ";
        }

    }
};

struct dvudol{
    vector<vector<int>> g;
    vector<int> used;
    int rev_cl(int c){
        return (c==1 ? 2 : 1);
    }
    void dfs(int v, int c = 1, int p =-1){
        used[v] = c;
        for(auto to : g[v]){
            if(p == to){
                continue;
            }
            if(!used[to]){
                dfs(to, rev_cl(c), v);
            }else{
//                cout <<used[to] << endl;
                if(used[to] == c){
                    cout << "nedvudol";
                    exit(0);
                }
            }
        }
    }

    dvudol(int n, int m){
        g.resize(n);
        used.resize(n);
        loop(i, 0, m){
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb(b);
            g[b].pb(a);
        }
        loop(i, 0, n){
            if(!used[i]){
                dfs(i);
            }
        }
        cout << "dvudol";


    }
};

// хранить только одну долю?
struct parsoh{
    vector<vector<int>> g;
    vector<int> used;
    vector<int> mt;
    bool dfs(int v){
        if(used[v]){
            return false;
        }
        used[v] = true;
        for(auto to : g[v]){
            if(mt[to] == -1 || dfs(to)){
                mt[to] = v;
                return true;
            }
        }
        return false;
    }

    parsoh(int n, int m){
        g.resize(n);
        used.resize(n);
        mt.resize(n, -1);
        loop(i, 0, m){
            int a, b;
            cin >> a >> b;
            a--, b--;
            g[a].pb(b);
            g[b].pb(a);
        }
        int cnt = 0;
        loop(i, 0, n){
            used.assign(n, 0);
            if(dfs(i)){
                cnt++;
            }
        }



    }
};

struct djikstramlogn{
    vector<vector<pair<int, int>>>g;
    int n;

    vector<int> start(int s){
        vector<int> d(n, inf);
        d[s] = 0;
        set<pair<int, int>> st;
        st.insert({0, s});
        while(!st.empty()){
            int v = st.begin()->second;
            st.erase(st.begin());
            for(auto [to, w] : g[v]){
                if(d[to] > d[v] + w){
                    st.erase({d[to], to});
                    d[to] = d[v] + w;
                    st.insert({d[to], to});
                }
            }
        }
        return d;
    }
};
struct djikstran2{
    vector<vector<pair<int, int>>>g;
    int n;

    vector<int> start(int s){
        vector<int> d(n, inf), a(n, 0);
        d[s] = 0;
        lp(n){
            int v = -1;
            loop(to, 0, n){
                if(!a[to] && (v == -1 || d[v] > d[to])){
                    v = to;
                }
            }

            a[v] = 1;
            for(auto [to, w] : g[v]){
                d[to] = min(d[to], d[v] + w);
            }
        }
        return d;
    }
};

struct hsh{
    vector<ll> h;
    vector<ll> pw;
    ll mod, k;
    ll sum(ll a, ll b){
        return (a%mod + b%mod) %mod;
    }
    ll sub(ll a, ll b){
        return (a%mod - b%mod+ mod )%mod;
    }
    ll mul(ll a, ll b){
        return (a%mod * b%mod) %mod;
    }
    hsh(string& a, ll md, ll l){
        int n= sz(a);
        mod = md;
        k = l;
        h.resize(sz(a));
        pw.resize(sz(a), 1);
        pw[1] = k;
        loop(i, 2, n){
            pw[i] = mul(pw[i-1], k);
        }
        h[0] = a[0];
        loop(i, 1, n){
            h[i] = sum(mul(h[i-1], k), a[i]);
        }
    }
    ll substr(ll l, ll r){
        if(l == 0){
            return h[r];
        }
        return sub(h[r], mul(h[l-1], pw[r-l+1]));

    }
};
vector<int> slow_zf(string s){
    int n = sz(s);
    vector<int> z(n, 0);
    int l = 0;
    int r = 0;
    for(int i = 1; i < n; i++){

        if(i <=r){
            z[i] = min(z[i-l], r-i+1);
        }
        while(i+z[i] < n && s[z[i]] == s[i + z[i]]){
            z[i]++;
        }
        if (i + z[i] - 1 > r) {
            r = i + z[i] - 1;
            l = i;
        }
    }

    return z;
}