题目描述

仓库管理系统维护着一个长度为 $n$ 的库存序列，初始时每一项都是 $0$。系统需要支持以下两种指令：

1. U k a 把序列中第 $k$ 个数修改为 $a$。
2. Z c s 设想这样一轮搬运：每一轮从序列中选出 $c$ 个正数，把它们各减去 $1$。询问是否有可能连续进行 $s$ 轮搬运。

注意每条询问都是独立的假想操作，并不会真的修改序列。

输入格式

第一行包含两个正整数 $n,m$，分别表示序列长度和指令条数。

接下来 $m$ 行，每行一条指令，格式如上所述。

输出格式

输出若干行。对于每条 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

提示

【数据范围】

对于 $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$。