Description

Diao Cha receives a task from the tax authority to investigate a merchant’s ledger and determine whether it is forged. The ledger records the income over $n$ months, where the income in month $i$ is $a_i$, $i=1,2,\ldots,n-1,n$. When $a_i>0$, it means the profit in that month is $a_i$ yuan; when $a_i<0$, it means the loss in that month is $|a_i|$ yuan. The total income over a period is the sum of the monthly incomes within that period.

Her task is carried out in secret. To investigate the ledger, she goes to work for the merchant. When the merchant is away, she peeks at the ledger, but she cannot take it out. Each time she peeks, she can only look at the income recorded for some continuous period, and she can remember only the total income over that period.

Now, she has peeked at the ledger $m$ times and thus remembered the total incomes over $m$ periods. Your task is to determine, based on these remembered totals, whether the ledger is fake.

Input Format

The first line contains a positive integer $w$, where $w<100$, indicating that there are $w$ test cases (that is, $w$ ledgers) to judge.

For each test case, the first line contains two positive integers $n$ and $m$, where $n<100, m<1000$, indicating how many months of income the ledger records and how many times she peeked at the ledger.

The next $m$ lines describe the $m$ pieces of information Diao Cha remembered after $m$ peeks. Each line contains three integers $s$, $t$ and $v$, meaning that the total income from month $s$ to month $t$ (including month $t$) is $v$. Here, assume $s$ is always less than or equal to $t$.

Output Format

Output $w$ lines, each containing true or false. The $i$-th line is true if and only if the $i$-th test case, i.e., the $i$-th ledger, is not fake; the $i$-th line is false if and only if the $i$-th test case, i.e., the $i$-th ledger, is fake.

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

Hint

Translated by ChatGPT 5