题目内容

给定一个长度为 $n$ 的非负整数序列 $a_1, a_2, \dots, a_n$，其元素总和为 $m$，即 $\sum_{i=1}^n a_i = m$。

定义该序列的波动值为相邻元素之差的绝对值之和：

同时，如果 $a_i eq a_{i+1}$，我们称位置 $i$ 为一个变化点。变化点的总数即 $\#\{ i \in [1, n-1] \mid a_i eq a_{i+1} \}$。

现在有 $q$ 次独立询问，每次询问给定两个整数 $k$ 和 $g$，请判断是否存在一个满足以下所有条件的序列 $a$：

• 元素总和等于 $m$；
• 变化点的数量不超过 $k$；
• 波动值 $V(a) \ge g$。

如果存在，回答 YES，否则回答 NO。

数据范围

• 测试用例数 $t$：$1 \le t \le 10^4$；
• 序列长度 $n$：$1 \le n \le 10^9$；
• 总和 $m$：$0 \le m \le 10^9$；
• 询问次数 $q$：$1 \le q \le 2 \times 10^5$，且所有测试用例的 $q$ 之和不超过 $2 \times 10^5$；
• 变化点上限 $k$：$0 \le k \le n-1$；
• 阈值 $g$：$0 \le g \le 10^{18}$。

输入描述

第一行包含一个整数 $t$，表示测试用例的数量。 对于每个测试用例：

• 第一行包含三个整数 $n, m, q$，分别表示序列长度、总和以及询问次数。
• 接下来 $q$ 行，每行包含两个整数 $k, g$，表示变化点上限和波动值阈值。

输出描述

对于每个询问，输出一行字符串，若存在满足条件的序列则输出 YES，否则输出 NO。

样例1

输入

1
4 6 4
1 6
2 12
2 13
0 0

输出

YES
YES
NO
NO

说明

该测试用例中 $n=4$，$m=6$，共有 4 个询问。

• 询问 1 6：变化点上限 $k=1$，此时最大波动值为 $m=6$，要求的 $g=6$ 可以达到，输出 YES。
• 询问 2 12：变化点上限 $k=2$，因为 $n \ge 3$ 且 $k \ge 2$，最大波动值为 $2m = 2 \times 6 = 12$，$g=12$ 可以达到，输出 YES。
• 询问 2 13：同样最大波动值为 12，但 $g=13 > 12$，无法达到，输出 NO。
• 询问 0 0：变化点上限 $k=0$ 要求所有元素相等，但 $m=6$ 无法被 $n=4$ 整除，因此不存在合法序列，即使 $g=0$ 也不可行，输出 NO。

样例2

输入

1
1 5 2
0 0
0 1

输出

YES
NO

说明

该测试用例中 $n=1$，$m=5$，共有 2 个询问。序列长度为 1，没有相邻元素，因此波动值恒为 $0$，变化点数量恒为 $0$。

• 询问 0 0：$k=0$ 时存在合法序列，且最大波动值 $0$ 满足 $0 \ge 0$，输出 YES。
• 询问 0 1：最大波动值 $0 < 1$，无法满足要求，输出 NO。

样例3

输入

1
2 10 3
1 10
1 11
0 0

输出

YES
NO
YES

说明

该测试用例中 $n=2$，$m=10$，共有 3 个询问。由于只有 2 个元素，最多存在 1 个变化点。

• 询问 1 10：$k=1$ 时最大波动值为 $m=10$，$g=10$ 可以达到，输出 YES。
• 询问 1 11：最大波动值为 10，$g=11 > 10$，无法达到，输出 NO。
• 询问 0 0：$k=0$ 要求两个元素相等，此时 $m=10$ 能被 $n=2$ 整除，存在序列 $[5,5]$，波动值为 $0$，$g=0$ 可以满足，输出 YES。