[HNOI2005]狡猾的商人

刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。

账本上记录了 $n$ 个月以来的收入情况，其中第 $i$ 个月的收入额为 $A_i$（$i = 1, 2, \ldots, n$）。当 $A_i$ 大于 $0$ 时表示这个月盈利 $A_i$ 元，当 $A_i$ 小于 $0$ 时表示这个月亏损 $A_i$ 元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。

刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。她趁商人不在时去偷看账本，可是她无法将账本偷出来，每次偷看账本时她都只能看某段时间内账本上记录的收入情况，并且她只能记住这段时间内的总收入。

现在，刁姹总共偷看了 $m$ 次账本，当然也就记住了 $m$ 段时间内的总收入，你的任务是根据记住的这些信息来判断账本是不是假的。

输入格式

第一行为一个正整数 $w$，表示有 $w$ 组数据，即 $w$ 个账本需要你判断。

每组数据的第一行为两个正整数 $n$ 和 $m$，分别表示对应的账本记录了多少个月的收入情况以及偷看了多少次账本。

接下来的 $m$ 行表示刁姹偷看 $m$ 次账本后记住的 $m$ 条信息，每条信息占一行，有三个整数 $s, t, v$，表示从第 $s$ 个月到第 $t$ 个月（包含第 $t$ 个月）的总收入为 $v$，这里假设 $s$ 总是小于等于 $t$。

输出格式

包含 $w$ 行，每行是 true 或 false：第 $i$ 行为 true 当且仅当第 $i$ 组数据（即第 $i$ 个账本）不是假的；第 $i$ 行为 false 当且仅当第 $i$ 个账本是假的。

样例输入

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

样例输出

true
false

样例解释

第一组数据的三条信息互不矛盾：由 $A_1+A_2 = 10$ 与 $A_1+A_2+A_3 = -5$ 可推出 $A_3 = -15$，与第三条信息一致。

第二组数据中，由 $A_1+\cdots+A_5 = 100$ 与 $A_3+A_4+A_5 = 50$ 可推出 $A_1+A_2 = 50$，但第三条信息给出 $A_1+A_2 = 51$，出现矛盾，因此账本是假的。

数据范围

• $w < 100$；
• $n < 100$，$m < 1000$。

来源与许可

本题为 HNOI 2005 试题「狡猾的商人」，题面与测试数据整理自 BZOJ 1202。

样例 1

输入

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

输出

true
false