$$$m$$$ 椅子按顺序排列成圆圈。椅子的编号从 $$$0$$$ 到 $$$m-1$$$。 $$$n$$$ 人们想坐在这些椅子上。他们中的第 $$$i$$$ 想要在他的左右两侧至少有 $$$a[i]$$$ 空椅子。
更正式地说,如果第 $$$i$$$ 人坐在第 $$$j$$$ 位椅子上,则其他人不得坐在以下椅子上: $$$(j-a[i]) \bmod m$$$, $$$(j-a[i]+1) \bmod m$$$, ... $$$(j+a[i]-1) \bmod m$$$, $$$(j+a[i]) \bmod m$$$。
决定在给定的限制下是否可以让所有人都坐下来。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^9$$$) — 人数和椅子数量。
下一行包含 $$$n$$$ 整数,$$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 第 $$$i$$$ 人两侧空椅子的最小数量。
保证所有测试用例的$$$n$$$总和不会超过$$$10^5$$$。
输出
对于每个测试用例,如果每个人都可以坐下来满足限制,则打印“YES”(不带引号),否则打印“NO”(不带引号)。
您可以按照您想要的任何大小写打印每个字母(因此,例如,字符串“yEs”、“yes”、“Yes”和“YES”都将被识别为肯定答案)。
示例
输入 #1
6 3 2 1 1 1 2 4 1 1 2 5 2 1 3 8 1 2 1 4 12 1 2 1 3 4 19 1 2 1 3
输出 #1
NO YES NO YES NO YES
注意
测试用例$$$1$$$:$$$n>m$$$,所以他们不能坐下。
测试用例 $$$2$$$:第一个人可以坐在第 $$$2$$$-nd 椅子上,第二个人可以坐在第 $$$0$$$-th 椅子上。他们都希望两边至少有 $$$1$$$ 空椅子,$$$1$$$ 和 $$$3$$$ 椅子都是免费的,所以这是一个很好的解决方案。
测试用例$$$3$$$:如果第二个人在某个地方坐下,他的右侧和左侧都需要$$$2$$$空椅子,所以不可能为第一个人找到位置,因为只有$$$5$$$椅子。
测试用例$$$4$$$:他们可以分别坐在$$$1$$$-st、$$$4$$$-th、$$$7$$$-th椅子上。