题目描述

土豆鸡厨神比赛 (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 都会被认为是肯定的答案。

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

YES
YES
YES
YES
NO
YES
NO
YES
NO