Problem Description

The Cook Chicken Potato Contest is one of the most famous competitions in the chef world. The venue always provides $k$ stoves, and the organizer Little $Q$ will divide the contestants into $k$ teams with the same number of people.

To test teamwork among contestants and make the contest more exciting, Little $Q$ will arrange the teams so that the skill gaps among contestants in the same team are as large as possible. Suppose the contestants' skills are $a_1,a_2,\ldots,a_n$, and the teams they belong to are $t_1,t_2,\ldots,t_n$. Little $Q$ defines the excitement of the contest as:

$$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}$$

Now, $n$ possible contestants are given in nondecreasing order of skill. Since a contestant's skill is not fixed, the $i$-th contestant is described by an interval $[l_i,r_i]$, meaning their actual skill in a contest can be any real number in this interval. Also, because the contestants' skills are monotonic nondecreasing by index, it is guaranteed that for all $\forall 1 \le i < j \le n$, we have $l_i \leq l_j, r_i \leq r_j$.

Little $Q$ has $q$ contest plans. In the $i$-th plan, contestants with indices between $L_i$ and $R_i$ will be invited. You need to help Little $Q$ determine whether there exists a way to assign teams such that the contest excitement may be at least $D_i$.

Input Format

This problem contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases.

Then the test cases follow. For each test case:

The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \times 10^5$, $1 \le k \le \min(5, n)$), representing the number of possible contestants and the number of teams.

The next $n$ lines each contain two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^{12}$), describing the possible skill range of the $i$-th contestant.

It is guaranteed that for all $\forall 1 \le i < n$, $l_i \le l_{i+1}$ and $r_i \le r_{i+1}$.

The next line contains an integer $q$ ($1 \le q \le 10^5$), indicating the number of contest plans.

The next $q$ lines each contain three integers $L_i$, $R_i$, and $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}$), meaning that in the $i$-th plan, contestants with indices from $L_i$ to $R_i$ will be invited, and Little $Q$ expects the excitement to be $D_i$.

It is guaranteed that $\sum n$ over all test cases does not exceed $10^6$, and $\sum q$ does not exceed $10^5$.

Output Format

For each test case, output $q$ lines. For the $i$-th line, output YES or NO, indicating whether Little $Q$'s expected value for the $i$-th plan may be achievable. You may output the answer in any letter case (uppercase or lowercase). For example, yEs, yes, Yes, and YES are all considered affirmative answers.

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

Hint

Translated by ChatGPT 5