Untitled

#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define sz(v) (v.size())
#define yes cout<<"Yes"<<'\n';
#define no cout<<"No"<<'\n';
#define endl '\n';
#define f(i,j,k) for(long long i=j;i<k;i++)
#define fb(i,j,k) for(long long i=j;i>=k;i--)
#define fs(i,j,k,p) for(long long i=j;i<k;i+=p)
#define fbs(i,j,k,p) for(long long i=j;i>=k;i-=p)
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ff first
#define ss second
#define pi 3.141592653589793238462
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pp ;
typedef vector<ll> vll;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
long long pow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
ll mod =1e9+7;

void add_divs(ll x, map<ll, ll>&divs){
    ll i = 2;
    while(i * i <= x){
        while (x % i == 0){
            divs[i]++;
            x /= i;
        }
        i++;
    }
    if(x > 1) divs[x]++;
}




ll n1;

ll mrg (ll x ,ll y )
{
    return x+y;
}

struct segment_tree
{
    vector<ll> tree;
    void clear()
    {
        tree.clear();
    }

    void init(int num, const vector<ll>& a)
    {
        n1 = num;
        tree.assign(4 * n1, 0ll);
        build(a);
    }

    void build(const vector<ll>& a, int id=0,int ns = 0, int ne = n1-1)
    {
        if(ns==ne){
            tree[id] = a[ns];
            return ;
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        build(a,l, ns, md);
        build(a,r, md+1, ne);
        tree[id] = mrg(tree[l],tree[r]);
    }


    ll query(int qs, int qe, int id=0, int ns=0, int ne=n1-1)
    {
        if(ns>qe || qs>ne){
            return 0; ///infnity
        }
        if(qs<=ns && qe>=ne){
            return tree[id];
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        ll ndl = query(qs, qe, l, ns, md);
        ll ndr = query(qs, qe,r, md+1,ne);
        return mrg(ndl,ndr );
    }

    void upd(int pos , int val , int id=0, int ns=0,int ne=n1-1)
    {
        if(ns>pos || pos>ne){
            return;
        }
        if(ns==ne){
            tree[id]=val;
            return ;
        }
        int l = 2*id+1;
        int r = l+1;
        int md = ns+(ne-ns)/2;
        upd(pos, val,l, ns, md);
        upd(pos, val, r, md+1, ne);
        tree[id] = mrg(tree[l],tree[r]);
    }
} st ;
int main()
{

}