scenery

Problem Description

你正在一处景点取景，你找到了 $n$ 处有趣的景色并打算给每处景色拍一张照片。一天可以被分为 $m$ 个时间段，你发现第 $i$ 处景色只有在一天中的第 $l_i \sim r_i$ 个时间段才能被拍摄到，并且拍摄这处景色需要消耗连续的 $t_i$ 个时间段（即需要选连续的 $t_i$ 个时间段用于拍摄景色 $i$，且所有选出的时间段需要在 $[l_i,r_i]$ 内）。你同一时间段只能拍摄一处景色，问能否顺利拍摄完所有 $n$ 处景色？ 保证 $l$ 序列不增，$r$ 序列不降。

Input

本题有多组数据。第一行一个正整数 $T$（$1\le T\le 2\times 10^3$），表示测试数据组数。 对于每组数据，第一行两个整数 $n,m$（$1 \le n,m \le 5000$）。 接下来 $n$ 行，每行三个整数 $l_i,r_i,t_i$（$1 \le l_i \le r_i \le m,1 \le t_i \le m$）。 保证 $\forall 1 < i \le n,l_i \le l_{i-1},r_i \ge r_{i-1}$。 保证 $\sum n^2$ 和 $\sum m^2$ 均不超过 $10000^2$。

Output

对于每组数据，如果能顺利拍摄所有 $n$ 处景色输出 YES，否则输出 NO。

Sample Input

5
5 12
4 6 2
3 9 2
1 11 3
1 11 1
1 12 2
6 8
4 5 1
4 6 1
4 6 3
2 6 1
1 7 1
1 7 2
4 10
5 7 1
4 7 1
1 9 2
1 10 3
3 5
3 3 3
2 3 1
2 5 1
4 12
5 7 1
3 10 2
2 11 3
1 11 1

Sample Output

YES
NO
YES
NO
YES

Source

2024“钉耙编程”中国大学生算法设计超级联赛（10）