解题思路

设数组为 $a_1,a_2,\dots,a_n$，满足

• $a_i \ge 0$
• $\sum_{i=1}^n a_i=m$
• 相邻不同的位置数不超过 $d$

并定义

题目内容

给定两个整数$n,m$，你需要构造一个长度为 $n$的非负整数数组$a=${$a_1,a_2,…,a_n$}，使其元素总和满足：

$\sum _{i=1}^na_i=m$

定义相邻差和：

$F(a)=\sum _{i=1}^{n−1}∣a_i−a_{i+1}∣$

本题有 $q$ 次独立询问。第$j$次询问给出一对整数 $(d,y)$，你最多只能让数组中 “相邻数值不同” 的边（我们将$i (1≤i≤n−1)$视为第$i$ 条边，连接相邻元素 $a_i$ 与 $a_{i+1}$）的数量不超过 $d$，即：

$\#\left\{ i \in [1, n-1] \mid a_i \neq a_{i+1} \right\} \le d$

并问在该限制下，是否存在某个数组 $a$ 使$F(a)≥y$。若存在，输出 $YES$；否则输出 $NO$。

注意：不同询问彼此独立，均基于同一对 $(n,m)$重新构造数组。

输入描述

每个测试文件均包含多组测试数据：

1. 第一行输入一个整数$t (1≤t≤10^4)$，表示测试用例数量。

2. 对于每个测试用例：

   • 第一行输入三个整数 $n,m,q (1≤n≤10^9;0≤m≤10^9;1≤q≤2×10^5)$；
   • 此后 $q$行，每行输入两个整数$d,y (0≤d≤n-1;0≤y≤10^{18})$。

3. 除此之外，保证全部测试用例的 $q$之和不超过 $2×10^5$。

输出描述

对于每个询问，输出一行 $YES$或 $NO$，表示是否存在满足限制的数组 $a$ 使$F(a)≥y$。

样例1

输入

2
5 7 5
0 0
1 7
1 8
2 14
2 15
1 3 2
0 0
0 1

输出

NO
YES
NO
YES
NO
YES
NO

说明

对测试用例一，$n=5,m=7$：

• 若 $d=0,y=0$：数组必须为常数列，但$m\ mod\ n≠0$无法构造，输出 $NO$；
• 若$d=1,y=7$：取$[7,0,0,0,0]$，边数为 $1$，$F=7≥7$，输出 $YES$；