[POI2015]LOG

题目描述

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

输入输出格式

输入格式


第一行包含两个正整数 $n,m$,分别表示序列长度和操作次数。 接下来 $m$ 行为 $m$ 个操作。

输出格式


包含若干行,对于每个 `Z` 询问,若可行,输出 `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

说明

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