template <class T>
struct Fenwick {
    const int n;
    vector<T> tr;
    Fenwick(int n) : n(n), tr(n + 1) {}
    void init(vector<T>& a, int m) {
        for (int i = 1; i <= m; i++) {
            tr[i] += a[i];
            int j = i + lowbit(i);
            if (j <= m) tr[j] += tr[i];
        }
    }
    void add(int x, T c) {
        for (int i = x; i <= n; i += lowbit(i))
            tr[i] += c;
    }
    T query(int x) {
        T ans = 0;
        for (int i = x; i; i -= lowbit(i))
            ans += tr[i];
        return ans;
    }
    T range_query(int l, int r) { return query(r) - query(l - 1); }
    T kth_min(int k) {  // 第k小 (树状数组上二分)
        int res = 0;
        for (int i = __lg(n); i >= 0; i--) {
            res += (1 << i);
            if (res > n || tr[res] >= k)
                res -= (1 << i);
            else
                k -= tr[res];
        }
        return res + 1;
    }
};

// 区间修改 + 区间查询
// 令d[i]是a[i]的差分数组  tr1[i] = d[i]   tr2[i] = d[i] * i
template <class T>
struct Fenwick {
    const int n;
    vector<T> tr1, tr2;
    Fenwick(int n) : n(n), tr1(n + 1), tr2(n + 1) {}
    void init(int n, vector<T>& v) {
        for (int i = 1; i <= n; i++)
            add(i, v[i] - v[i - 1]);
    }
    void add(int x, T c) {
        for (int i = x; i <= n; i += lowbit(i))
            tr1[i] += c, tr2[i] += c * x;
    }
    void range_add(int l, int r, T x) { add(l, x), add(r + 1, -x); }
    T query(int p) {
        T res = 0;
        for (int i = p; i; i -= lowbit(i))
            res += (p + 1) * tr1[i] - tr2[i];
        return res;
    }
    T range_query(int l, int r) { return query(r) - query(l - 1); }
};