void dfs(int tl, int tr, int sum, vector<Item> &q, bitset<250001> &dp, vector<int> &cnt)
{
    vector<Item> ql, qr;
    for (auto &x : q)
    {
        if (x.l <= tl && tr <= x.r)
        {
            sum += x.val;
            dp |= dp << x.val;
        }
    }
    if (tl == tr)
    {
        for (int i = 0; i < 250001 && 2 * i < sum; ++i)
        {
            if (!dp[i])
                continue;
            ++cnt[sum - 2 * i];
        }
        return;
    }
    int tm = tl + tr >> 1;
    for (auto &x : q)
    {
        if (x.l <= tl && tr <= x.r)
            continue;
        if (intersect(x.l, x.r, tl, tm))
            ql.inb(x);
        if (intersect(x.l, x.r, tm + 1, tr))
            qr.inb(x);
    }
    q.clear();
    bitset<250001> ndp = dp;
    dfs(tl, tm, sum, ql, dp, cnt);
    dfs(tm + 1, tr, sum, qr, ndp, cnt);
}