// T must + -
// id 1~n
template<typename T,size_t M,typename OpPlus=plus<T>,typename OpMinus=minus<T>>
struct BIT
{
    static int lowbit(int x) { return x&(-x); }
    constexpr static OpPlus opp{};
    constexpr static OpMinus opm{};
    static T tmp[M+1];

    T tree[M+1]; // tree[i] -> sum of [i-lowbit(i)+1,i]
    int n;
    void init(int n_)
    {
        n=n_;
        for(int i=1;i<=n;i++) tree[i]=T(0);
    }
    void init(int n_,T v[]) // v[0 ~ n_-1]
    {
        n=n_; tmp[0]=T(0);
        for(int i=1;i<=n;i++) tmp[i]=opp(tmp[i-1],v[i]);
        for(int i=1;i<=n;i++) tree[i]=opm(tmp[i],tmp[i-lowbit(i)]);
        // for(int i=0;i<n;i++) add(i,v[i]);
    }
    void add(int p,T V)
    { for(;p<=n;p+=lowbit(p)) tree[p]=opp(tree[p],V); }
    T sum(int p)
    {
        T ans(0);
        for(;p;p-=lowbit(p)) ans=opp(ans,tree[p]);
        return ans;
    }
    T sum(int l,int r) { return opm(sum(r),sum(l-1)); }
};

// T must define + -
// id x:1~n y:1~m
template<typename T,
         size_t MN,
         size_t MM,
         typename OpPlus=plus<T>,
         typename OpMinus=minus<T>>
struct BIT
{
    static int lowbit(int x) { return x&(-x); }
    constexpr static OpPlus opp{};
    constexpr static OpMinus opm{};

    T tree[MN+1][MM+1]; // tree[i] -> sum of [i-lowbit(i)+1,i]
    int n,m;
    void init(int n_,int m_)
    {
        n=n_; m=m_;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) tree[i][j]=T(0);
    }
    void init(int n_,int m_,T v[MN][MM]) // v[0 ~ n_-1]
    {
        init(n_,m_);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) add(i,j,v[i][j]);
    }
    void add(int x,int y,T V)
    { 
        for(;x<=n;x+=lowbit(x)) 
            for(int i=y;i<=m;i+=lowbit(i)) tree[x][i]=opp(tree[x][i],V); 
    }
    T sum(int x,int y)
    {
        T ans(0);
        for(;x;x-=lowbit(x)) 
            for(int i=y;i;i-=lowbit(i)) ans=opp(ans,tree[x][i]);
        return ans;
    }
    T sum(int minx,int maxx,int miny,int maxy)
    {
        return opm(opp(sum(maxx,maxy),sum(minx-1,miny-1)),
            opp(sum(maxx,miny-1),sum(minx-1,maxy)));
    }
};