题目描述

某列火车行驶在 $c$ 个城市之间（出发的城市编号为 $1$，结束达到的城市的编号为 $c$），假设该列火车有 $s$ 个座位，现在有 $r$ 笔预订票的业务。现在想对这 $r$ 笔业务进行处理，看哪些预定能满足，哪些不能满足。

一笔预定由 $o$、$d$、$n$ 三个整数组成，表示从起点站 $o$ 到目标站 $d$ 需要预定 $n$ 个座位。一笔预定能满足是指该笔业务在行程范围内有能满足的空座位，否则就不能满足。一笔业务不能拆分，也就是起点和终点站不能更改，预定的座位数目也不能更改。所有的预定需求按给出先后顺序进行处理。

请你编写程序，计算出哪些预定业务能满足，哪些不能满足。

输入格式

第一行输入三个整数 $c$、$s$、$r$。

接下来的 $s$ 行每行输出三个整数 $o$、$d$、$n$，分别表示每一笔预定业务。

输出格式

对每笔业务，输出一行，仅包含一个字母。如果可以满足要求则输出 T，否则输出 N。

样例输入

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

样例输出

T
T
N
N

数据规模与约定

对于所有数据，$1\leq c,s,r\leq 6\times 10^4$，$1\leq o<d\leq c$，$1\leq n\leq s$。