//ДЕРЕВО ОТРЕЗКОВ
#include <iostream>
#include <vector>

using namespace std;

struct SegmentTree{
    int get(int l, int r){
        return get(0, 0, n-1, l, r);
    }
    void set(int p, int x){
        set(0, 0, n-1, p, x);
    }
    int get(int id, int sl, int sr, int ql, int qr){
        if (ql<=sl && sr<=qr){
            return data[id];
        }
        int m=(sl+sr)/2;
        if (qr<=m){
            return get(id*2+1,sl,m,ql,qr);
        }
        if (ql>m){
            return get(id*2+2,m+1,sr,ql,qr);
        }
        return get(id*2+1,sl,m,ql,qr)+get(id*2+2,m+1,sr,ql,qr);
    }
    void set(int id, int sl, int sr, int p, int x){
        if (sl==sr){
            data[id]+=x;
            return ;
        }
        int m = (sl + sr) / 2;
        if (p <= m){
            set (id*2+1, sl, m , p, x);
        }
        else{
            set(id * 2 + 2, m+1, sr, p, x);
        }
        data[id] = data[id*2+1] + data[id*2+2];
    }
    int n;
    vector <int> data;
    SegmentTree(int n_){
        n=n_;
        data.resize(n*4);
    }
    int build(const vector<int> &a){
        build (0,0,n-1,a);
    }
    void build(int id, int sl, int sr, const vector<int> &a){
        if (sl==sr){
            data[id]=a[sl];
            return;
        }
        int m = (sl+sr)/2;
        build(id*2+1, sl, m, a);
        build(id*2+2, m+1, sr, a);
        data[id]=data[id*2+1]+data[id*2+2];
    }
    void add(int id, int sl, int sr, int ql, int qr, int x){
        if (ql<=sl&&sr<=qr){
            data[id]+=x;
            return;
        }
        int m = (sl+sr)/2;
        if( qr<= m) {
            add(id*2+1, sl, m, ql, qr, x);
        }
        if (m<qr){
            add(id*2+2, m+1, sr, ql, qr, x);
        }
    }
    int get(int id, int sl, int sr, int p){
        if (sl==sr){
            return data[id];
        }
        int m = (sl+sr)/2;
        if (p<=m){
            return get(id*2+1, sl, m, p)+data[id];
        }
        return get(id*2+2, m+1, sr, p)+data[id];
    }
};

//ПОСТРОЕНИЕ ДЕРЕВА ЧЕРЕЗ SET РАБОТАЕТ ЗА O(NlogN), ЧЕРЕЗ build - ЗА O(N);

int main(){

    return 0;
}