题目描述

在一条无穷长的数轴上摆放着 $n$ 个箱子。第 $i$ $(1 \leq i \leq n)$ 个箱子在时刻 $0$ 位于数轴 $a_i$ 处，而你希望在时刻 $t_i$ 以及之后的所有时刻，这个箱子处在数轴的 $b_i$ 处。保证序列 $[a_1, \ldots, a_n]$ 和 $[b_1, \ldots, b_n]$ 单调递增。

为此，从时刻 $0$ 开始的每个单位时间里，你可以将某个箱子在数轴上移动一个单位长度，也可以什么都不做。你需要保证任意时刻每个点上都只有一个箱子。形式化地，每个单位时间里你可以按照以下方式进行一次操作，也可以不进行操作：

选择任意一个箱子。记其编号为 $i$，它目前的位置为 $p_i$。

选择一个方向 $d \in {\pm1}$，其中 $d = 1$ 代表向右，$d = -1$ 代表向左。你需要保证数轴上 $(p_i + d)$ 处没有箱子。

将 $i$ 号箱子从点 $p_i$ 移动到点 $(p_i + d)$ 处。

你想知道，是否存在一种操作方法同时满足所有箱子的要求，即对于任意 $1 \leq i \leq n$，第 $i$ 个箱子在时刻 $t_i$ 以及之后的所有时刻都处于数轴的 $b_i$ 处。

输入格式

从文件 move.in 中读入数据。

本题有多组测试数据。输入的第一行两个整数 $c$, $T$，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 $c = 0$。

对于每组测试数据，第一行一个整数 $n$，表示箱子的个数，接下来 $n$ 行，第 $i$ $(1 \leq i \leq n)$ 行三个整数 $a_i$, $b_i$, $t_i$，分别表示第 $i$ 个箱子的初始位置、目标位置和时刻要求。

输出格式

输出到文件 move.out 中。

对于每组测试数据，输出一行一个字符串 Yes 或 No，表示是否存在一种操作方法同时满足所有箱子的要求。

样例 1

输入：

0 2
2
4 5 1
6 7 1
3
4 5 3
7 6 1
10 8 4

输出：

No
Yes

该组样例共有 $2$ 组测试数据。

• 对于第一组测试数据，答案是否定的。将 $1$ 号箱子由点 $4$ 移动到点 $5$，并将 $2$ 号箱子由点 $6$ 移动到点 $7$，至少需要两个单位时间，因此不可能在时刻 $1$ 同时满足两个箱子的条件。

• 对于第二组测试数据，答案是肯定的，例如如下方法同时满足了所有箱子的要求：

  • 在时刻 $0$ 至时刻 $1$ 的一个单位时间，将 $2$ 号箱子由点 $7$ 移动到点 $6$；

  • 在时刻 $1$ 至时刻 $2$ 的一个单位时间，将 $3$ 号箱子由点 $10$ 移动到点 $9$；

  • 在时刻 $2$ 至时刻 $3$ 的一个单位时间，将 $1$ 号箱子由点 $4$ 移动到点 $5$；

  • 在时刻 $3$ 至时刻 $4$ 的一个单位时间，将 $3$ 号箱子由点 $9$ 移动到点 $8$；

  • 在之后的所有单位时间，什么都不做。

样例 2

见选手目录下的 move/move2.in 与 move/move2.ans。

该组样例共有 6 组测试数据，所有数据均满足特殊性质 A。其中每组测试数据的 n 分别为 $7、7、7、200、3\,000、2 \times 10^5$，且测试数据 $1 \sim 3$ 满足 $a_i, b_i \leq 15$，测试数据 4 满足 $a_i, b_i \leq 3,000$。

样例 3

见选手目录下的 move/move3.in 与 move/move3.ans。

该组样例共有 6 组测试数据，所有数据均满足特殊性质 B。其中每组测试数据的 n 分别为 $7、7、7、200、3\,000、2 \times 10^5$，且测试数据 $1 \sim 3$ 满足 $a_i, b_i \leq 15$，测试数据 4 满足 $a_i, b_i \leq 3,000$。

样例 4

见选手目录下的 move/move4.in 与 move/move4.ans。

该组样例共有 6 组测试数据，所有数据均满足特殊性质 C。其中每组测试数据的 n 分别为 $7、7、7、200、3\,000、2 \times 10^5$，且测试数据 1 \sim 3 满足 $a_i, b_i \leq 15$，测试数据 4 满足 $a_i, b_i \leq 3,000$。

样例 5

见选手目录下的 move/move5.in 与 move/move5.ans。

该组样例共有 6 组测试数据。其中每组测试数据的 n 分别为 $7、7、7、200、3\,000、2 \times 10^5$，且测试数据 $1 \sim 3$ 满足 $a_i, b_i \leq 15$，测试数据 4 满足 $a_i, b_i \leq 3,000$。

子任务

对于所有测试点，

• $1 \leq T \leq 6$

• $1 \leq n \leq 2 \times 10^5$

• $\forall 1 \leq i \leq n$, $1 \leq a_i, b_i \leq 10^9$, $0 \leq t_i \leq 10^{16}$

• $\forall 1 \leq i < n$, $a_i < a_{i+1}$, $b_i < b_{i+1}$

测试点编号	n ≤	a_i, b_i ≤	特殊性质
1	7	15	A
2, 3			无
4	200	3,000	A
5			B
6, 7			无
8	3,000	10^9	A
9			B
10, 11			无
12	$8 \times 10^4$	$5 \times 10^5$	A
13			B
14, 15			C
16~18			无
19, 20	$2 \times 10^5$	$10^9$	B
21, 22			C
23~25			无

• 特殊性质 A：$\forall 1 \leq i < j \leq n$, $t_i = t_j$

• 特殊性质 B：$\forall 1 \leq i \leq n$, $a_i \leq b_i$ 且 $\forall 1 \leq i < n$, $b_i < a_{i+1}$

• 特殊性质 C：$\forall 1 \leq i \leq n$, $a_i \leq b_i$