// lazy part is pending -> other code is fine
class SGtree
{
    vi seg, lazy;

public:
    SGtree(int n)
    {
        // Adjust deafault value (if needed) --> size = [4*arr.size()]
        seg.resize(4 * n + 1, 0);
        lazy.resize(4 * n + 1, 0);
    }

    void build(vi &arr, int l, int r, int ind)
    {
        if (l == r)
        {
            // Change accordingly (for single element)
            seg[ind] = arr[l];
            return;
        }

        int mid = (l + r) / 2;
        build(arr, l, mid, 2 * ind + 1);
        build(arr, mid + 1, r, 2 * ind + 2);

        // Assuming operation is sum of range[l, r]
        seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
    }

    // query on [l, r] where l and r are fixed
    int tell(int l, int r, int a, int b, int ind)
    {
        // Adjust deafault value of lazy (if needed)
        if (lazy[ind])
        {
            if (a != b)
            {
                // if (a!=b) -> not leaf -> have childs
                lazy[2 * ind + 1] = lazy[ind];
                lazy[2 * ind + 2] = lazy[ind];
            }

            // Assuming operation is sum of range[l, r]
            // Update accordingly -> added val (b-a+1) times {bcz sum query on index[a...b]}
            seg[ind] += lazy[ind] * (b - a + 1);

            lazy[ind] = 0; // Adjust deafault value of lazy (if needed)
        }

        if (l <= a && b <= r)
        {
            return seg[ind];
        }

        if (r < a || b < l) // NO overlap
        {
            // Return the default value
            return 0;
        }

        int mid = (a + b) / 2;
        int x = tell(l, r, a, mid, 2 * ind + 1);
        int y = tell(l, r, mid + 1, b, 2 * ind + 2);

        // Do the operation
        return x + y;
    }

    // point update of arr[x] = val
    void update(int l, int r, int ind, int x, int val)
    {
        if (l == r)
        {
            seg[ind] = val;
            return;
        }

        int mid = (l + r) / 2;
        if (x <= mid)
        {
            update(l, mid, 2 * ind + 1, x, val);
        }
        else
        {
            update(mid + 1, r, 2 * ind + 2, x, val);
        }

        // Assuming operation is sum of range[l, r]
        seg[ind] = seg[2 * ind + 1] + seg[2 * ind + 2];
    }

    // range update from {arr[l].....arr[r]} to val
    void lazyPropagation(int l, int r, int a, int b, int ind, int val)
    {
        if (l <= a && b <= r)
        {
            // If 2 consecutive updates on same node
            lazy[ind] += val;
            cout << lazy[ind] << " " << ind << " " << a << " " << b << endl;
            return;
        }

        if (r < a || b < l) // NO overlap
        {
            return;
        }

        int mid = (a + b) / 2;
        lazyPropagation(l, r, a, mid, 2 * ind + 1, val);
        lazyPropagation(l, r, mid + 1, b, 2 * ind + 2, val);
    }
};