书籍分配

题目描述

现在有$n$个书架，一开始没有任何书。有两种操作：

1. $U$ $k$ $a$：第$k$个书架上书的数量变成$a$。
2. $Z$ $c$ $s$：询问假如（也就是说询问之间互不影响）有$s$个人来买书，每个人选择$c$个不同的非空书架各买一本书（这会使对应书架上书的数量减一），则是否存在一种方案使得每个人都能买到$c$本书。

输入格式

第一行两个正整数$n$和$m$，分别表示书架的个数和操作个数。

接下来$m$行，分别表示$m$个操作，操作格式见【题目描述】。

输出格式

包含若干行，对于每个询问，如果可行则输出$TAK$，否则输出$NIE$。

数据范围与提示

• 对于$4\%$的数据，$n=1$；
• 对于$50\%$的数据，$n$，$m \leq 10^{3}$；
• 对于$100\%$的数据，$1 \leq n$，$m \leq 10^{6}$，$1 \leq k$，$c \leq n$，$0 \leq a \leq 10^{9}$，$1 \leq s \leq 10^{9}$。

样例

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

10 15
U 4 5
U 3 7
U 8 8
Z 3 3
U 7 1
U 9 8
U 10 99
Z 7 1
U 1 133
U 2 851
Z 5 10
Z 2 10
U 6 7
U 7 100
Z 3 187

TAK
NIE
TAK
TAK
NIE