//inverse mod
If MOD is a prime number, then for any integer a such that 
a is not divisible by MOD:
a ^ (MOD - 1) = 1
a ^ (MOD - 2) = a ^(-1) (% MOD)

// debug container
template<typename T>
auto debugContainer(T&  t) {
	for (auto& x : t) {
		cout << x << ' ';
	}
	cout << endl;
}

ll modPow(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        exp >>= 1;
        base = (base * base) % mod;
    }
    return res;
}

// Print out error:
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {
	cout << '\n';
}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << ' ';
	err(++it, args...);
}

// debug map
template<typename T>
auto debugContainer2(T&  t) {
	for (auto& [x, y] : t) {
		cout << x << ' ' << y << endl;
	}
	cout << endl;
}

// 0-indexed
class SegTree{
    struct Node{
        int left, right;
        int minV, maxV, sum, minIndex, maxIndex;
        int lazy;
        Node():left(0), right(0), minV(INT_MAX), maxV(INT_MIN), lazy(0){}
        void Set(int v, int i){
            minV = maxV = sum = v;
            minIndex = maxIndex = i;
        }
    };
    vector<Node> tree;
    vector<int> input;
public:
    SegTree(vector<int> _input){
        int m = _input.size();
        tree.resize(m * 4);
        input = _input;
        Build(0, 0, m - 1);
    }
    void Propagate(int node){
        if(!tree[node].lazy) return;
        //Apply pending update
        int tLeft = tree[node].left, tRight = tree[node].right;
        tree[node].sum = tree[node].lazy * (tRight - tLeft + 1);
        tree[node].minV = tree[node].lazy;
        tree[node].maxV = tree[node].lazy;
        //If not a leaf node, propagate
        tree[node * 2 + 1].lazy = tree[node].lazy;
        tree[node * 2 + 2].lazy = tree[node].lazy;
        //Reset
        tree[node].lazy = 0;
    }
    void UpdateRange(int node, int left, int right, int val){
        //Ensure pending udpate are applied before this operation
        Propagate(node);
        
        int tLeft = tree[node].left, tRight = tree[node].right;
        //no overlap
        if(left > tRight || right < tLeft) return;
        //total overlap
        if(left <= tLeft && right >= tRight){
            tree[node].lazy = val;
            Propagate(node);//???
            return;
        }
        UpdateRange(node * 2 + 1, left, right, val);
        UpdateRange(node * 2 + 2, left, right, val);
    }
    void Maintain(int root){
        int leftChild = (root << 1) + 1;
        int rightChild = (root << 1) + 2;
        tree[root].sum = tree[leftChild].sum + tree[rightChild].sum;
        tree[root].minV = min(tree[leftChild].minV, tree[rightChild].minV);
        tree[root].maxV = max(tree[leftChild].maxV, tree[rightChild].maxV);
        tree[root].minIndex = tree[leftChild].minV < tree[rightChild].minV ? tree[leftChild].minIndex : tree[rightChild].minIndex;
        tree[root].maxIndex = tree[leftChild].maxV < tree[rightChild].maxV ? tree[rightChild].maxIndex : tree[leftChild].maxIndex;
    }
    void Build(int root, int start, int end){
        tree[root].left = start;
        tree[root].right = end;
        if(start == end){
            tree[root].Set(input[start], start);
            return;
        }
        int mid = (start + end) >> 1;
        //build left child
        Build((root << 1) + 1, start, mid);
        Build((root << 1) + 2, mid + 1, end);
        Maintain(root);
    }
    int QueryMin(int root, int l, int r){
        Propagate(root);
        int left = tree[root].left, right = tree[root].right;
        if(l == left && r == right) return tree[root].minIndex;//tree[root].minV;
        int mid = (left + right) >> 1; 
        if(r <= mid) return QueryMin((root << 1) + 1, l, r);
        else if(l >= mid + 1) return QueryMin((root << 1) + 2, l, r);
        int leftMinIndex = QueryMin((root << 1) + 1, l, mid);
        int rightMinIndex = QueryMin((root << 1) + 2, mid + 1, r);
        return input[leftMinIndex] < input[rightMinIndex] ? leftMinIndex : rightMinIndex;    
    }
    void Update(int root, int pos, int val){
        int left = tree[root].left, right = tree[root].right;
        if(left == right && left == pos){
            tree[root].Set(val, pos);
            return;
        }
        int mid = (left + right) >> 1;
        if(pos <= mid) Update((root << 1) + 1, pos, val);
        else Update((root << 1) + 2, pos, val);
        Maintain(root);
    }
    }
};

sample question 3072:

void Update(int node, int val){
    int tLeft = tree[node].left, tRight = tree[node].right;
    if(tLeft == tRight){
        tree[node].count += 1;
        return;
    }
    int mid = (tLeft + tRight) >> 1;
    if(val <= mid) Update(val, node * 2 + 1, tLeft, mid);
    else Update(val, node * 2 + 2, mid + 1, tRight);
    //maintain
    tree[node].count = tree[node * 2 + 1].count + tree[node * 2 + 2].count;
}
int Query(int node, int left, int right){
    int tLeft = tree[node].left, tRight = tree[node].right;
    if(left > right) return 0;
    if(left <= tLeft && right >= tRight) return tree[node].count;
    int mid = (tLeft + tRight) >> 1;
    return Query(node * 2 + 1, left, min(right, mid))
    + Query(node * 2 + 2, max(left, mid + 1), right);
}