md 普通线段树过不了 艹

警示后人

不要用普通线段树写！（WA #8

再怎么卡常都是过不了的

Cao

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n,m,Max[N<<2],Min[N<<2],num[N<<2],c,x;
long long sum[N<<2],ans;
char opt;

char buf[N+5],*p1,*p2;
#define gc (p1==p2&&(p2=(p1=buf)+fread(buf,1,N,stdin),p1==p2)?EOF:*p1++)

inline int read()
{
    int r=0;
    char c=gc;
    while(!isdigit(c)) c=gc;
    while(isdigit(c))
    { 
        r=(r<<1)+(r<<3)+c-48;
        c=gc;
    }
    return r;
}

inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}

inline void pushup(int x)
{
    Max[x]=max(Max[ls(x)],Max[rs(x)]);
    Min[x]=min(Min[ls(x)],Min[rs(x)]);
    sum[x]=sum[ls(x)]+sum[rs(x)];
    num[x]=num[ls(x)]+num[rs(x)];
}
inline void update(int p,int l,int r,int L,int k)
{
    if(l==r)
    {
        sum[p]=Max[p]=Min[p]=k;
        num[p]=(k>0);
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid) update(ls(p),l,mid,L,k);
    else       update(rs(p),mid+1,r,L,k);
    pushup(p);
}
inline long long querysum(int p,int l,int r,int s)
{
    if(Max[p]<s) return sum[p];
    if(Min[p]>=s)
    {
        c-=(r-l+1);
        return 0;
    }
    int mid=(l+r)>>1;
    return querysum(ls(p),l,mid,s)+querysum(rs(p),mid+1,r,s);
}

// inline int querycnt(int p,int l,int r,int s)
// {
//  // if(l==r) puts("qwq");
//  // printf("[%lld %lld] %lld\n",l,r,Max[p]);
//  if(Min[p]>=s) return r-l+1;
//  if(Max[p]<s) return 0;
//  int mid=(l+r)>>1;
//  return querycnt(ls(p),l,mid,s)+querycnt(rs(p),mid+1,r,s);
// }

signed main()
{
    // printf("%lld\n",read());
    n=read(); m=read();
    // build(1,1,n);
    // puts("qwq");
    while(m--)
    {
        while(!isalpha(opt=gc));
        c=read(); x=read();
        if(opt=='U') update(1,1,n,c,x);
        else
        {
            if(num[1]<c)
            {
                printf("%s\n","NIE");
                continue;
            }
            // printf("%lld\n",c);
            ans=querysum(1,1,n,x);
            printf("%s\n",(c*x<=ans?"TAK":"NIE"));
        }
    }

}