WA on #5,8,10

#include<bits/stdc++.h>
namespace fast_IO
{
	#define Getchar() p1==p2 and (p2=(p1=Inf)+fread(Inf,1,1<<21,stdin),p1==p2)?EOF:*p1++
	#define Putchar(c) p3==p4 and (fwrite(Ouf,1,1<<21,stdout),p3=Ouf),*p3++=c
	char Inf[1<<21],Ouf[1<<21],*p1,*p2,*p3=Ouf,*p4=Ouf+(1<<21);
	inline void read(int &x,char c=Getchar())
	{
		bool f=c!=45;
		x=0;
		while(c<48 or c>57) c=Getchar(),f&=c!=45;
		while(c>=48 and c<=57) x=(x<<3)+(x<<1)+(c^48),c=Getchar();
		x=f?x:-x;
	}
	inline void write(int x)
	{
		if(x<0) Putchar(45),x=-x;
		if(x>=10) write(x/10),x%=10;
		Putchar(x^48);
	}
	inline void read(long long &x,char c=Getchar())
	{
		bool f=c!=45;
		x=0;
		while(c<48 or c>57) c=Getchar(),f&=c!=45;
		while(c>=48 and c<=57) x=(x<<3)+(x<<1)+(c^48),c=Getchar();
		x=f?x:-x;
	}
	inline void write(long long x)
	{
		if(x<0) Putchar(45),x=-x;
		if(x>=10) write(x/10),x%=10;
		Putchar(x^48);
	}
	inline bool inrange(const char &ch)
	{
		if(ch>=48 and ch<=57 or ch>=65 and ch<=90 or ch>=97 and ch<=122) return true;
		return false;
	}
	inline void read(std::string &st,char c=Getchar())
	{
		st.clear();
		while(!inrange(c)) c=Getchar();
		while(inrange(c)) st+=c,c=Getchar();
	}
	inline void write(std::string st)
	{
		for(int i=0;i<st.size();i++) Putchar(st[i]);
	}
	inline void read(char &ch)
	{
		ch=Getchar();
		while(!inrange(ch)) ch=Getchar();
	}
	inline void write(const char &ch)
	{
		Putchar(ch);
	}
};
using namespace fast_IO;
long long ans;
struct Treap_node
{
	int val,w,cnt,siz;
	long long sum;
	Treap_node *lc,*rc;
	Treap_node(int Val)
	{
		val=Val,sum=Val,w=rand(),cnt=siz=1,lc=rc=nullptr;
	}
	inline void push()
	{
		siz=(lc==nullptr?0:lc->siz)+(rc==nullptr?0:rc->siz)+cnt;
		sum=(lc==nullptr?0:lc->sum)+(rc==nullptr?0:rc->sum)+val*cnt;
	}
};
class Treap
{
private:
	Treap_node *root;
	inline int askrank(Treap_node *rt,int val)
	{
		if(rt==nullptr) return 0;
		int left=rt->lc==nullptr?0:rt->lc->siz;
		if(val<rt->val) return askrank(rt->lc,val);
		else
		{
			ans+=1ll*rt->cnt*rt->val+(rt->lc==nullptr?0:rt->lc->sum);
			if(val==rt->val) return left;
			else return askrank(rt->rc,val)+left+rt->cnt;
		}
	}
	inline Treap_node *right(Treap_node *rt)
	{
		Treap_node *q=rt->lc;
		rt->lc=q->rc,q->rc=rt,rt->push(),q->push();
		return q;
	}
	inline Treap_node *left(Treap_node *rt)
	{
		Treap_node *q=rt->rc;
		rt->rc=q->lc,q->lc=rt,rt->push(),q->push();
		return q;
	}
	inline Treap_node *add(Treap_node *rt,int val)
	{
		Treap_node *ret=rt;
		if(rt==nullptr) ret=new Treap_node(val);
		else if(val==rt->val) rt->cnt++;
		else if(val<rt->val)
		{
			rt->lc=add(rt->lc,val);
			if(rt->w<rt->lc->w) ret=right(rt);
		}else
		{
			rt->rc=add(rt->rc,val);
			if(rt->w<rt->rc->w) ret=left(rt);
		}
		ret->push();
		return ret;
	}
	inline Treap_node *del(Treap_node *rt,int val)
	{
		if(rt==nullptr) return nullptr;
		if(val==rt->val)
		{
			if(rt->cnt>1)
			{
				rt->cnt--,rt->push();
				return rt;
			}
			if(rt->lc==nullptr && rt->rc==nullptr)
			{
				delete rt;
				return nullptr;
			}
			Treap_node *ret=rt;
			if(rt->rc==nullptr || rt->lc!=nullptr && rt->lc->w>rt->rc->w)
				ret=right(rt),ret->rc=del(ret->rc,val);
			else ret=left(rt),ret->lc=del(ret->lc,val);
			if(ret!=nullptr) ret->push();
			return ret;
		}
		val<rt->val?rt->lc=del(rt->lc,val):rt->rc=del(rt->rc,val);
		if(rt!=nullptr) rt->push();
		return rt;
	}
public:
	// Treap()
	// {
	// 	root=new Treap_node(-1e9),root->rc=new Treap_node(1e9),root->push();
	// }
	inline void add(int val)
	{
		root=add(root,val);
	}
	inline void del(int val)
	{
		root=del(root,val);
	}
	inline int askrank(int val)
	{
		return askrank(root,val);
	}
};
Treap treap;
int n,m,a[1000010],cnt;
char op;
int main()
{
	read(n),read(m);
	for(int i=1;i<=n;i++) treap.add(0);
	for(int i=1,x,y,pos;i<=m;i++)
	{
		read(op),read(x),read(y);
		if(op=='U')
		{
			if(a[x]==0 && y!=0) cnt++;
			else if(a[x]!=0 && y==0) cnt--;
			treap.del(a[x]),a[x]=y,treap.add(y);
		}else
		{
			ans=0,pos=treap.askrank(y);
			if(ans+(n-pos)*y>=x*y && cnt>=x) write("TAK\n");
			else write("NIE\n");
		}
	}
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}