问题 5029 --书籍分配

5029: 书籍分配

题目描述

  现在有 $n$ 个书架,一开始没有任何书。有两种操作:
U k a:第 $k$ 个书架上书的数量变成 $a$。
Z c s:询问假如(也就是说询问之间互不影响)有 $s$ 个人来买书,每个人选择 $c$ 个不同的非空书架各买一本书(这会使对应书架上书的数量减一),则是否存在一种方案使得每个人都能买到 $c$ 本书。

输入

第一行两个正整数 $n$ 和 $m$,分别表示书架的个数和操作个数。
接下来 $m$ 行,分别表示 $m$ 个操作,操作格式见【题目描述】。

输出

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

样例输入输出

输入#1 复制
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
输出#1 复制
NIE
TAK
NIE
TAK
输入#2 复制
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
输出#2 复制
TAK
NIE
TAK
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$。

序号 标题 作者 发表时间 费用 订购数 操作