#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int n,m,a[N],tree[N];
int lobit(int x){
	return x&-x;
}
void add(int x,int c){
	for(int i=x;i<=n;i+=lobit(i)){
		tree[i]+=c;
	}
}
int query(int x){
	int res = 0;
	for(int i=x;i>=1;i-=lobit(i)){
		res+=tree[i];
	}
	return res;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		add(i,x);
	}
	for(int i=1;i<=m;i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			add(x,y);
		}
		else{
			cout<<query(y)-query(x-1)<<endl;
		}
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int n,m,a[N],tree[N];
int lobit(int x){
	return x&-x;
}
void add(int x,int c){
	for(int i=x;i<=n;i+=lobit(i)){
		tree[i]+=c;
	}
}
int query(int x){
	int res = 0;
	for(int i=x;i>=1;i-=lobit(i)){
		res+=tree[i];
	}
	return res;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		int x = a[i]-a[i-1];
		add(i,x);
	}
	for(int i=1;i<=m;i++){
		int op,x,y,k;
		cin>>op>>x;
		if(op==1){
			cin>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		else{
			cout<<query(x)<<'\n';
		}
	}
	return 0;
}

/*
100 550 200 600 300
1 4 2 5 3
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+5;
int n,a[N],tree[N],res;
int b[N],id[N];
int lobit(int x){
	return x&-x;
}
void add(int x,int c){
	for(int i=x;i<=n;i+=lobit(i)){
		tree[i]+=c;
	}
}
int query(int x){
	int res = 0;
	for(int i=x;i>=1;i-=lobit(i)){
		res+=tree[i];
	}
	return res;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i] = a[i];
	}
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
		id[i] = lower_bound(b+1,b+n+1,a[i])-b;
	}
	for(int i=1;i<=n;i++){
		res+=query(n)-query(id[i]);
		add(id[i],1);
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,k,a[N],sum[N],b[N],id[N];
int tree[N];
int lobit(int x){
	return x&-x;
}
void add(int x,int c){
	for(int i=x;i<=n+1;i+=lobit(i)){
		tree[i]+=c;
	}
}
int query(int x){
	int res = 0;
	for(int i=x;i>=1;i-=lobit(i)){
		res+=tree[i];
	}
	return res;
}

signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]-=k;
	}
	sum[0] = 0;
	id[1] = sum[0];
	for(int i=1;i<=n;i++){
		sum[i] = sum[i-1]+a[i];
		b[i+1] = sum[i];
	}
	sort(b+1,b+n+2);
	for(int i=0;i<=n;i++){
		id[i+1] = lower_bound(b+1,b+n+2,sum[i])-b;
	}
	int res = 0;
	for(int i=1;i<=n+1;i++){
		res+=query(id[i]);
		add(id[i],1);
	}
	cout<<res<<endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,m,a[N],ans[N],tree[N],lst[N];
struct node{
	int l,r,id;
}p[N];
bool cmp(node a,node b){
	if(a.r==b.r)return a.l<b.l;
	else return a.r<b.r;
}
int lobit(int x){
	return x&-x;
}
void add(int x,int c){
	for(int i=x;i<=n;i+=lobit(i)){
		tree[i]+=c;
	}
}
int query(int x){
	int res = 0;
	for(int i=x;i>=1;i-=lobit(i)){
		res+=tree[i];
	}
	return res;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>p[i].l>>p[i].r;
		p[i].id = i;
	}
	sort(p+1,p+m+1,cmp);
	int l=1;
	for(int i=1;i<=m;i++){
		while(l<=p[i].r){
			if(!lst[a[l]]){
				lst[a[l]] = l;
				add(l,1);
			}
			else{
				add(lst[a[l]],-1);
				lst[a[l]] = l;
				add(l,1);
			}
			l++;
		}
		if(p[i].l==1)ans[p[i].id] = query(p[i].r);
		else ans[p[i].id] = query(p[i].r)-query(p[i].l-1);
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6+5;
int n,m,c,a[N],ans[N],tree[N],lst[N],lst2[N];
struct node{
	int l,r,id;
}p[N];
bool cmp(node a,node b){
	if(a.r==b.r)return a.l<b.l;
	else return a.r<b.r;
}
int lobit(int x){
	return x&-x;
}
void add(int x,int c){
	for(int i=x;i<=n;i+=lobit(i)){
		tree[i]+=c;
	}
}
int query(int x){
	int res = 0;
	for(int i=x;i>=1;i-=lobit(i)){
		res+=tree[i];
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>c>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>p[i].l>>p[i].r;
		p[i].id = i;
	}
	sort(p+1,p+m+1,cmp);
	int l=1;
	for(int i=1;i<=m;i++){
		while(l<=p[i].r){
			if(!lst[a[l]]){
				lst[a[l]] = l;
			}
			else if(!lst2[a[l]]){
				lst2[a[l]] = lst[a[l]];
				lst[a[l]] = l;
				add(lst2[a[l]],1);
			}
			else{
				add(lst2[a[l]],-1);
				lst2[a[l]] = lst[a[l]];
				lst[a[l]] = l;
				add(lst2[a[l]],1);
			}
			l++;
		}
		if(p[i].l==1)ans[p[i].id] = query(p[i].r);
		else ans[p[i].id] = query(p[i].r)-query(p[i].l-1);
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<'\n';
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
int n,m,tree[2][N],a[N],val[N],t[N],id[N],tt;
unordered_map<int,int>mp;
struct node{
	char op;
	int x,y;
}p[N];
int lobit(int x){
	return x&-x;
}
void add(int x,int c,int id){
	for(int i=x;i<=tt;i+=lobit(i)){
		tree[id][i]+=c;
	}
}
int query(int x,int id){
	int res = 0;
	for(int i=x;i>=1;i-=lobit(i)){
		res+=tree[id][i];
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	int cnt = 0;
	for(int i=1;i<=m;i++){
		char op;
		int x,y;
		cin>>op>>x>>y;
		p[i] = {op,x,y};
		val[i] = y;
		t[i] = y;
	}
	sort(t+1,t+m+1);
	tt = unique(t+1,t+m+1)-t;
	for(int i=1;i<tt;i++){
		mp[t[i]] = i;
	}
	for(int i=1;i<=m;i++){
		char op;
		int x,y;
		op = p[i].op,x=p[i].x,y=p[i].y;
		if(op=='U'){
			if(a[x]==0){
				int pos = mp[y];
				add(pos,1,0);
				add(pos,y,1);
			}
			else{
				int oldpos = mp[a[x]];
				int newpos = mp[y];
				add(oldpos,-1,0);
				add(newpos,1,0);
				add(oldpos,-a[x],1);
				add(newpos,y,1);
			}
			a[x] = y;
		}
		else{
			//大于等于s的数的个数
			int cnt = query(tt-1,0)-query(mp[y]-1,0);
			//小于s的数的和
			int sum = query(mp[y]-1,1);
		//	cout<<sum<<" "<<cnt<<endl;
			if(sum>=y*(x-cnt))cout<<"TAK"<<'\n';
			else cout<<"NIE"<<'\n';
		}
	}
	return 0;
}