Farmer John 有 𝑠 只奶牛，和 𝑛 个独立的篱笆，每个篱笆里可以圈养一些奶牛。出于一种奇♂️怪的偏好，Farmer John 把篱笆排成了一排。第 𝑖 个篱笆圈养的奶牛数量为 𝑎𝑖，显然我们有 ∑𝑛𝑖=1𝑎𝑖=𝑠。而且，处于 Farmer John 的癖好，他要求对于每个 𝑖 都有 𝑎𝑖>0。
Bessie 认为一个农场是“幸运的”当且仅当你可以找到一个区间 [𝑙,𝑟]，使得 ∑𝑟𝑖=𝑙𝑎𝑖=𝑘。
而得寸进尺的 Bessie 认为一个农场是“牛逼的”当且仅当不管 Farmer John 怎么安置他的奶牛，该农场都是“幸运的”。
现在有 𝑡(1≤𝑡≤105) 组询问，每组询问给出 𝑠,𝑛 和 𝑘(1≤𝑠,𝑛,𝑘≤1018,𝑛≤𝑠)，询问这个农场是不是“牛逼的”。
由于是区间问题，我们考虑先将其转换为两点问题。考虑 𝑏𝑖=∑𝑖𝑗=1𝑎𝑖，于是我们有 {𝑏0=0𝑏𝑛=𝑠。如果存在一对 ⟨𝑖,𝑗⟩ 满足 𝑏𝑗−𝑏𝑖=𝑘，那显然这个农场是幸运的。由于 𝑎𝑖>0，每一个 𝑏𝑖 都是两两不同的。于是问题就转化成了，在 1∼𝑠 中选出 𝑛 个数，使得这些数中不存在 𝑘，且不存在一对 ⟨𝑖,𝑗⟩ 满足 𝑗−𝑖=𝑘。
下面我们贪心地考虑最多能选出多少个满足条件的数。
考虑到不能有 𝑘 这个条件，我们把 𝑘 的倍数和不是 𝑘 的倍数的数分开讨论，对于不是 𝑘 倍数的数，如果我们选了 𝑥，那我们就不能选 𝑥+𝑘 了（如果 𝑥+𝑘≤𝑠 的话）。于是我们考虑对每 2𝑘 个划分为一段，这样除了最后一段不满的，就有 ⌊𝑠2𝑘⌋ 段，而每一段我们可以贪心地选择 1∼𝑘−1，这样保证了最后留下的 𝑠 mod 2𝑘 个数能尽量多取，于是这对于不是 𝑘 倍数的数，这 ⌊𝑠2𝑘⌋ 段可以选择 ⌊𝑠2𝑘⌋⋅(𝑘−1) 个数。然后我们考虑是 𝑘 倍数，由于不能选择 𝑘，我们只能选择 2𝑘 的倍数。这样这 ⌊𝑠2𝑘⌋ 段我们就能选取 ⌊𝑠2𝑘⌋ 个数。于是前 ⌊𝑠2𝑘⌋ 段一共最多能选取 ⌊𝑠2𝑘⌋⋅𝑘 个数。
然后我们考虑最后留下的 𝑠 mod 2𝑘 个数，我们不难发现最多只能选这里面前 𝑘−1 个数了（第 𝑘 个数不能选了是因为我们已经选了原序列中第 𝑘⋅⌊𝑠2𝑘⌋ 个数了）。因此，这一部分最多能选 min{𝑠 mod 2𝑘,𝑘−1} 个数。
然而上面那段忘记了一个条件，那就是第 𝑠 个数是必须要选的，因为 𝑏𝑛=𝑠。但是大部分情况下这没有关系，因为如果第 𝑠 个数没有选的话，那我们肯定选择了第 𝑠−𝑘 个数（因为我们是贪心选最多的，如果第 𝑠−𝑘 个数和第 𝑠 个数都不选的话，那就不是最优的了，因为可以选一个使所选数加一），于是我们把第 𝑠−𝑘 个数删去，选择第 𝑠 个数即可。唯一的影响在于如果当 𝑠=𝑘 的时候，那既然第 𝑠 个数一定要选，那么答案就只能是 YES 了。
所以，我们最终只要比较 ⌊𝑠2𝑘⌋⋅𝑘+min{𝑠 mod 2𝑘,𝑘−1} 与 𝑛 的大小即可得出答案。