void insert(int r, int x, int y, int a, int lx, int dy, int rx, int uy){
  //  printf("r%d %d %d %d %d\n",r,lx,dy,rx,uy);
    tree[r] += a;
    if(lx+1==rx || dy+1==uy) return;
    int mx = (lx+rx)>>1, my = (dy+uy)>>1, r4 = r<<2;
    if(x>=lx&&x<mx){
        if(y>=dy&&y<my){
            insert(r4+1,x,y,a,lx,dy,mx,my);
        }
        else{
       // if(y>=my&&y<uy){
            insert(r4+2,x,y,a,lx,my,mx,uy);
        }
    }
    else{
   // if(x>=mx&&x<rx){
        if(y>=dy&&y<my){
            insert(r4+3,x,y,a,mx,dy,rx,my);
        }
        else{
       // if(y>=my&&y<uy){
            insert(r4+4,x,y,a,mx,my,rx,uy);
        }
    }
}

int get(int r,int x1, int y1, int x2, int y2, int lx, int dy, int rx, int uy){
    if(x1>=x2 || y1>=y2) return 0;
    if(x1==lx && y1==dy && x2==rx && y2==uy || tree[r]==0) return tree[r];
    int sum = 0, mx = (lx+rx)>>1, my = (dy+uy)>>1, r4 = r<<2;
    int mx1 = max(x1,mx),mx2 = min(x2,mx), my1 = max(y1,my), my2 = min(y2,my);
    sum += get(r4+1,x1,y1,mx2,my2,lx,dy,mx,my);
    sum += get(r4+2,x1,my1,mx2,y2,lx,my,mx,uy);
    sum += get(r4+3,mx1,y1,x2,my2,mx,dy,rx,my);
    sum += get(r4+4,mx1,my1,x2,y2,mx,my,rx,uy);
    return sum;
}