假设 $$$a_1, a_2, \dots, a_n$$$ 是长度为 $$$n$$$ 的已排序整数序列,使得 $$$a_1 \leq a_2 \leq \dots \leq a_n$$$。
对于每个 $$$1 \leq i \leq n$$$,前 $$$i$$$ 项 $$$a_1, a_2, \dots, a_i$$$ 的前缀和 $$$s_i$$$ 定义为 $$$$$$ s_i = \sum_{k=1}^i a_k = a_1 + a_2 + \dots + a_i。 $$$$$$
现在你得到了前缀和的最后 $$$k$$$ 项,它们是 $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$。您的任务是确定这是否可行。
正式地,给定 $$$k$$$ 整数 $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$,任务是检查是否存在序列 $$$a_1, a_2, \dots, a_n$$$ 使得
1. $$$a_1 \leq a_2 \leq \dots \leq a_n$$$,以及
2. 对于所有 $$$n-k+1 \leq i \leq n$$$,$$$s_i = a_1 + a_2 + \dots + a_i$$$。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。以下行包含每个测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) 和 $$$k$$$ ($$$1 \leq k \leq n$$$),分别表示序列 $$$a$$$ 的长度和前缀和的项数。
每个测试用例的第二行包含 $$$k$$$ 整数 $$$s_{n-k+1}, \dots, s_{n-1}, s_{n}$$$ ($$$-10^9 \leq s_i \leq 10^9$$$ 对于每个 $$$n-k+1 \leq i \leq n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,如果可能,则输出“YES”(不带引号),否则输出“NO”(不带引号)。
在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入 #1
4 5 5 1 2 3 4 5 7 4 -6 -5 -3 0 3 3 2 3 4 3 2 3 4
输出 #1
Yes Yes No No
注意
在第一个测试用例中,我们有唯一的序列 $$$a = [1, 1, 1, 1, 1]$$$。
在第二个测试用例中,我们可以选择,例如$$$a = [-3, -2, -1, 0, 1, 2, 3]$$$。
在第三个测试用例中,前缀和定义了唯一的序列 $$$a = [2, 1, 1]$$$,但它没有排序。
在第四个测试用例中,可以证明不存在具有给定前缀和的序列。