拜特国国家铁路决定与时俱进，推出城际特快（InterCity）连接。由于缺乏高效的机车、干净的车厢和笔直的铁轨，目前只能开通一条这样的线路。另一个障碍是缺乏任何用于座位预订的计算机系统。编写该系统的核心部分就是你的任务。

为简单起见，我们假设城际特快线路穿过依次编号为 $1$ 到 $c$ 的城市（起点站编号为 $1$，$c$ 为终点站编号）。列车共有 $s$ 个座位，在任何两个相邻车站之间运送的乘客数量都不允许超过 $s$。

计算机系统需要依次接收预订请求，并确定是否可以满足这些请求。如果在铁路的给定区间内列车有足够的空余座位，则接受该请求。否则，该请求将被拒绝。不允许部分接受请求，例如仅接受部分区间或减少乘客人数。接受请求后，列车中的空余座位数将被更新。请求按照到达的顺序依次处理。

任务

编写一个程序：

• 从标准输入读取线路描述和请求预订的列表，
• 计算哪些请求将被接受，哪些将被拒绝，
• 向标准输出写入所有请求的答案。

输入格式

第一行包含三个整数 $c$，$s$ 和 $r$（$1 \le c \le 60\,000$，$1 \le s \le 60\,000$，$1 \le r \le 60\,000$），它们之间用单个空格分隔。这些数字分别表示：铁路线上的城市数量、列车中的座位数以及请求的数量。

接下来的 $r$ 行中写有连续的请求。第 $i+1$ 行描述了第 $i$ 个请求。描述由三个整数 $o$，$d$ 和 $n$（$1 \le o < d \le c$，$1 \le n \le s$）组成，它们之间用单个空格分隔。它们分别表示：起点站编号、终点站编号和请求的座位数。

输出格式

你的程序应该向标准输出写入 $r$ 行。第 $i$ 行应该包含且仅包含一个字符：

• T（表示“是”）——如果第 $i$ 个请求被接受，
• N（表示“否”）——否则。

样例

输入样例 1

4 6 4
1 4 2
1 3 2
2 4 3
1 2 3

输出样例 1

T
T
N
N