P15555 [CCPC 2025 哈尔滨站] 比赛

土豆鸡厨神比赛 (Cook Chicken Potato Contest) 是厨师界最为知名的赛事之一。赛场场地固定提供 $k$ 个灶台，参赛选手会被主办方小 $Q$ 分成 $k$ 个**人数相同**的队伍来进行比赛。 为了考验选手之间的团队配合，以及为比赛增加更多看点，小 $Q$ 在安排选手队伍会使相同队伍的选手实力差距**尽量大**。假定参加比赛的选手的实力分别为 $a_1,a_2,\ldots,a_n$，以及他们所属于的队伍分别为 $t_1, t_2,\ldots,t_n$，小 $Q$ 定义比赛的精彩度为： $$ D=\mathop{\min}_{1 \le i < j \le n} \begin{cases} |a_i - a_j| & t_i = t_j \\ +\infty & t_i \neq t_j \end{cases} $$ 现在按照按实力顺序从小到大给定 $n$ 名可能会参加比赛的选手。由于选手的实力并不固定，因此会用一个区间 $[l_i,r_i]$ 来描述第 $i$ 名选手，表示其在某场比赛的实际实力可能会是该区间的**任意实数**。又由于选手的按编号实力单调不降，因此保证对于 $\forall 1 \le i < j \le n$，有 $l_i \leq l_j, r_i \leq r_j$。 小 $Q$ 有 $q$ 个办赛计划，其中第 $i$ 个计划会邀请编号在 $L_i$ 和 $R_i$ 之间的选手参加，你需要帮小 $Q$ 计算是否存在一种分配选手队伍的方式，使得比赛的精彩度**可能**不低于 $D_i$。

本题包含多组测试数据。输入第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据组数。 接下来依次给出测试数据，对于每组测试数据， 第一行包含两个整数 $n$, $k$ ($1 \le n \le 5 \times 10^5 $, $1 \le k \le \min(5, n)$)，表示可能的选手数量以及队伍的数量。 接下来 $n$ 行的第 $i$ 行包含两个整数 $l_i$, $r_i$ ($0 \le l_i \le r_i \le 10^{12}$)，表示第 $i$ 名选手可能发挥出的实力。 保证 $\forall 1 \le i < n$，有 $l_i \le l_{i+1},r_i \le r_{i+1}$。 接下来一行包含一个整数 $q$ ($1 \le q \le 10^5$)，表示办赛计划的数量。 接下来 $q$ 行第 $i$ 行包含两个整数 $L_i$, $R_i$, $D_i$ ($1 \le L_i \le R_i \le n, k \mid (R_i - L_i + 1), 0 \le D_i \le 10^{12}$)，表示第 $i$ 个办赛计划会邀请标号在 $L_i$ 到 $R_i$ 之间的选手，小 $Q$ 预期的精彩度为 $D_i$。 保证所有测试数据的 $\sum n$ 不超过 $10^6$，$\sum q$ 不超过 $10^5$。

每组测试数据输出 $q$ 行，第 $i$ 输出 ``YES`` 或 ``NO`` 分别表示小 $Q$ 第 $i$ 个计划的预期是否有可能被达成。你可以以任意形式输出答案（大写或小写），比如 ``yEs``，``yes``， ``Yes`` 和 ``YES`` 都会被认为是肯定的答案。