struct node1{
    int l,r;
    ll sum;
    node1 *lft,*rgt;
    inline int mid(){return(l+r)>>1;}
    node1(int l, int r){
        this->l = l, this->r = r;
        this->sum = 0, lft = rgt = 0;
    }
    void create_needed(){
        if(!lft) lft = new node1(l,mid());
        if(!rgt) rgt = new node1(mid()+1,r);
    }
    void update(int pos, ll v){
        if(l == r){
            sum+=v;
            return;
        }
        create_needed();
        int mid = (l+r)>>1;
        if(pos <= mid) lft->update(pos,v);
        else rgt->update(pos,v);
        sum = lft->sum+rgt->sum;
    }
    ll query(int l, int r){
        if(this->l == l && this->r == r) return sum;
        create_needed();
        int mid = (this->l+this->r)>>1;
        if(r <= mid) return lft->query(l,r);
        else if(l > mid) return rgt->query(l,r);
        return lft->query(l,mid)+rgt->query(mid+1,r);
    }
};

struct node2{
    int l,r;
    node1 *data;
    node2 *lft,*rgt;
    inline int mid(){return(l+r)>>1;}
    node2(int l, int r){
        this->l = l, this->r = r;
        this->data = new node1(1,num_cols);
        this->lft = this->rgt = 0;
    }
    void create_needed(){
        if(!lft) lft = new node2(l,mid());
        if(!rgt) rgt = new node2(mid()+1,r);
    }
    void update(int row, int col, ll v){
        data->update(col,v);
        if(l == r) return;
        create_needed();
        int mid = (l+r)>>1;
        if(row <= mid) lft->update(row,col,v);
        else rgt->update(row,col,v);
    }
    ll query(int rl, int rr, int cl, int cr){
        if(l == rl && r == rr) return data->query(cl,cr);
        create_needed();
        int mid = (l+r)>>1;
        if(rr <= mid) return lft->query(rl,rr,cl,cr);
        else if(rl > mid) return rgt->query(rl,rr,cl,cr);
        return lft->query(rl,mid,cl,cr)+rgt->query(mid+1,rr,cl,cr);
    }
};