#include<bits/stdc++.h>
using namespace std;
int lowbit(const int & x){
	return x&-x;
}
template<typename T>
struct Fenwick{
	T* a;
	int Fenwick_size;
	Fenwick(const int & len=0) : Fenwick_size(len){
		a=new T[len+1]();
		Fenwick_size=len;
	} 
	~Fenwick(){
		delete[] a;
	}
	int size() const{
		return Fenwick_size;
	}
	void new_Fenwick(const int & len=0){
		delete[] a;
		a=new T[len+1]();
		Fenwick_size=len;
	}
	T query(int x){
		T sum{};
		while(x>0){
			sum+=a[x];
			x-=lowbit(x);
		}
		return sum;
	}
	T query(const int & l,const int & r){
		return query(r)-query(l-1);
	}
    bool add(int x,const T& s){
    	if(x<1||x>Fenwick_size) return false;
		while(x<=Fenwick_size){
			a[x]+=s,x+=lowbit(x);
		}
		return true;
	}
	bool update(const int & x,const T& old_value,const T& new_value){
		if(x<1||x>Fenwick_size) return false;
		add(x,new_value-old_value);
		return true;
	}
};