狡猾的商人

题目描述

Y 同学接到一个任务，为税务部门调查一位商人的账本，以确定账本是否被伪造。

账本上记录了 $N$ 个月以来的收入情况，其中第 $i$ 个月的收入额记为 $A_i$（$1 \le i \le N$）。当 $A_i > 0$ 时表示这个月盈利 $A_i$ 元，当 $A_i < 0$ 时表示这个月亏损 $|A_i|$ 元。一段时间内的总收入，定义为这段时间内每个月收入额的总和。

Y 同学为了秘密进行调查，在商人处打工并趁机偷看账本。每次偷看时，她只能查阅某段连续时间内的收入情况，并且只记住了这段时间内的总收入。

现在，Y 同学总共查阅了 $M$ 次账本，记住了 $M$ 段连续时间内的总收入。请你根据这些信息，判断账本是否存在伪造。即判断是否存在至少一组合法的收入序列 $A$ 能够同时满足这 $M$ 个条件；若不存在，说明信息中存在逻辑矛盾，账本必然是伪造的。

输入格式

第一行包含一个正整数 $W$，表示有 $W$ 组数据（即 $W$ 个独立的账本）需要判断。

对于每组测试数据： 第一行包含两个正整数 $N$ 和 $M$，分别表示账本记录的月数以及 Y 同学查阅账本的次数。 接下来的 $M$ 行，每行包含三个整数 $S, T, V$，表示从第 $S$ 个月到第 $T$ 个月（包含第 $T$ 个月）的总收入 $\sum_{i=S}^T A_i = V$。保证 $S \le T$。

输出格式

输出共 $W$ 行，每行一个字符串 true 或 false。 其中第 $i$ 行为 true 当且仅当第 $i$ 组数据的信息不存在矛盾（即账本可能不是假的）；第 $i$ 行为 false 当且仅当第 $i$ 组数据的信息存在矛盾（即账本一定是假的）。

样例

样例输入 #1

2
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51

样例输出 #1

true
false

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le W \le 99$，$1 \le N \le 99$，$1 \le M \le 999$，$1 \le S \le T \le N$，且所有的 $V$ 均在 32 位有符号整数的表示范围内。