题目描述

题目译自 XXII Olimpiada Informatyczna — II etap Logistyka

Bajtazar 经营一家物流公司，客户常需运送大宗货物，单辆卡车装不下，他就派出车队。有时，司机比卡车多，备用司机便以乘客身份同行。每辆卡车可载任意多乘客。车队可随时停车，停车时所有卡车停下，司机可随意换车或交换驾驶任务，停车次数无限制。

为提升道路安全，字节城交通部对卡车司机的工作时长设限。每位司机通过体检后，其驾照会注明单次行程可驾驶的公里数。

Bajtazar 请你编写程序，管理他的 $n$ 名司机团队，处理两种事件：

• 更新第 $i$ 名司机的驾照记录。初始时无记录，未获记录的司机不得开车。
• 查询能否派出 $c$ 辆卡车的车队，完成 $s$ 公里的行程。司机可作乘客或换车，每条行程单独处理，下个车队在上个返回后出发。

输入格式

第一行包含两个整数 $n, m$ $(1 \leq n, m \leq 1000000)$，分别表示司机数和事件数。
接下来的 $m$ 行描述事件：

• 更新事件：字母 U 和两个整数 $k, a$ $(1 \leq k \leq n, 0 \leq a \leq 10^9)$，表示第 $k$ 名司机此后可驾驶 $a$ 公里。
• 查询事件：字母 Z 和两个整数 $c, s$ $(1 \leq c \leq n, 1 \leq s \leq 10^9)$，询问能否用 $c$ 辆卡车完成 $s$ 公里的行程。

输出格式

若输入有 $z$ 个查询，输出 $z$ 行，第 $i$ 行包含一个字符串 TAK 或 NIE，表示第 $i$ 个查询的答案。

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

附加样例

1. $n=1$，多个更新和查询，包含是和否的回答；
2. $n=1000$，每位司机可驾驶 $1000$ 公里，查询 $1000$ 辆卡车行驶 $1$ 公里；
3. $n=500000$，每位司机可驾驶 $1$ 公里，查询 $1$ 辆卡车行驶 $500000$ 公里。

数据范围与提示

对于 $33\%$ 的数据，$n, m \leq 1000$。
对于 $66\%$ 的数据，$a, s \leq 10^6$。