#4378. [POI2015]Logistyka

内存限制:256 MiB 时间限制:20 Sec

题目描述

维护一个长度为n的序列,一开始都是0,支持以下两种操作:
1.U k a 将序列中第k个数修改为a。
2.Z c s 在这个序列上,每次选出c个正数,并将它们都减去1,询问能否进行s次操作。
每次询问独立,即每次询问不会对序列进行修改。

输入格式

第一行包含两个正整数n,m(1<=n,m<=1000000),分别表示序列长度和操作次数。
接下来m行为m个操作,其中1<=k,c<=n,0<=a<=10^9,1<=s<=10^9。

输出格式

包含若干行,对于每个Z询问,若可行,输出TAK,否则输出NIE。

样例

样例输入


			
3 8
U 1 5
U 2 7
Z 2 6
U 3 1
Z 2 6
U 2 2
Z 2 6
Z 2 1

样例输出


			
NIE
TAK
NIE
TAK

数据范围与提示

鸣谢Claris