Problem D. Competition

The Cook Chicken Potato Contest is one of the most famous events in the culinary world. The venue provides $k$ fixed cooking stations, and the organizer, Little Q, divides the participants into $k$ teams of equal size to compete.

To test the teamwork among participants and add more excitement to the competition, when arranging the teams, Little Q aims to maximize the strength difference between members of the same team. Assuming the strengths of the participants are $a_1, a_2, \dots, a_n$ and their respective teams are $t_1, t_2, \dots, t_n$, Little Q defines the "excitement" of the competition as:

$$D = \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}$$

The $n$ potential participants are given in non-decreasing order of their strength. Since a participant's strength is not fixed, an interval $[l_i, r_i]$ is used to describe the $i$-th participant, representing that their actual strength in a competition could be any real number within this interval. Because the participants' strengths are non-decreasing with their index, it is guaranteed that for all $1 \le i < n$, $l_i \le l_{i+1}$ and $r_i \le r_{i+1}$.

Little Q has $q$ competition plans. In the $i$-th plan, participants with indices between $L_i$ and $R_i$ are invited. You need to help Little Q determine if there exists a way to assign the participants to teams such that the excitement of the competition can be at least $D_i$.

Input

There are multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^5$) representing the number of test cases. For each test case:

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

The next $n$ lines each contain two integers $l_i, r_i$ ($0 \le l_i \le r_i \le 10^{12}$), representing the possible strength range of the $i$-th participant. It is guaranteed that for $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$), representing the number of competition plans.

The next $q$ lines each contain three integers $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}$), representing that the $i$-th plan invites participants with indices from $L_i$ to $R_i$, and Little Q's expected excitement is $D_i$.

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

Output

For each test case, output $q$ lines. The $i$-th line should output "YES" or "NO", indicating whether Little Q's expectation for the $i$-th plan can be achieved. You may output the answer in any case (e.g., "yEs", "yes", "Yes", and "YES" are all considered affirmative).

Examples

Input 1

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

Output 1

YES
YES
YES
YES
NO
YES
NO
YES
NO