Byteasar 拥有一家物流公司。他的客户经常需要运输大量的货物，这些货物无法装入单辆卡车。在这种情况下，Byteasar 会派遣一个车队。有时，车队中的司机人数多于卡车数量，多余的司机可以作为乘客随行。我们假设每辆卡车可以搭载任意数量的乘客。司机可以在任何时刻选择让车队停下。在继续行程之前，司机可以登上任意一辆卡车，并更换驾驶员。沿途停靠的次数没有上限或下限。

为了提高道路交通安全，Byteotian 交通部对卡车司机驾驶的时间设定了限制。每位司机在通过定期心理物理测试后，其驾照上会有一个记录，说明他们在单次行程中可以驾驶多少公里。

Byteasar 请你编写一个程序，帮助他管理他的 $n$ 名卡车司机。程序必须处理以下两种类型的事件：

• 更新第 $i$ 位司机驾照上的记录。我们假设初始时没有任何司机的驾照上有记录。在获得记录之前，司机不能驾驶卡车。
• 关于派遣一个包含 $c$ 辆卡车的车队行驶 $s$ 公里路程的可行性查询。如前所述，在途中，司机可以作为乘客，并且可以自由更换。运输任务是按顺序处理的，即只有在前一个车队返回后，下一个车队才会出发。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 1\,000\,000$)，由一个空格分隔，分别表示司机的人数和事件的数量。接下来的 $m$ 行指定了事件。

如果是更新记录，该行包含字母 U 和两个整数 $k$ 和 $a$ ($1 \le k \le n, 0 \le a \le 1\,000\,000\,000$)，表示从此刻起，第 $k$ 位司机在单次行程中可以驾驶 $a$ 公里。如果是查询，该行包含字母 Z 和两个整数 $c$ 和 $s$ ($1 \le c \le n, 1 \le s \le 1\,000\,000\,000$)，表示关于派遣 $c$ 辆卡车行驶 $s$ 公里路程的查询。

数据范围

在总分 33% 的测试中，满足附加条件 $n, m \le 1000$。在总分 66% 的测试中，满足附加条件 $a, s \le 1\,000\,000$。

输出格式

如果输入包含 $z$ 个查询，则应向标准输出打印 $z$ 行：第 $i$ 行应包含单词 TAK（波兰语中的 YES）或 NIE（波兰语中的 NO），具体取决于第 $i$ 个输入查询的答案。

样例

输入 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

说明

样例评分测试： 1ocen：一名司机，多次记录更新和查询，包含肯定和否定答案； 2ocen：1000 名司机，每人可以驾驶 1000 公里；我们想要在 1 公里的路线上派遣 1000 辆卡车； 3ocen：500 000 名司机，每人可以驾驶 1 公里；我们正在 500 000 公里的路线上派遣一辆卡车。