昨天,Dima 发现了一个空数组,并决定向其中添加一些整数。他可以无限次执行以下操作:
- 将任意整数添加到数组的左端或右端。
- 那么,只要数组中存在一对相同的相邻元素,就会用它们的和来替换它们。
可以证明,数组中最多同时存在一对这样的对。
例如,如果数组是$$$[3, 6, 4]$$$,我们在左边添加数字$$$3$$$,那么数组首先会变成$$$[3, 3, 6, 4]$$$,然后前两个元素会被$$$6$$$替换,数组就会变成$$$[6, 6, 4]$$$,然后—— $$$[12, 4]$$$。
执行操作后 正是 $$$k$$$次,他认为自己获得了长度为$$$n$$$的数组$$$a$$$,但他不记得自己应用了哪些操作。确定是否存在可以从空数组生成给定数组 $$$a$$$ 的 $$$k$$$ 操作序列,或者确定这是不可能的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例描述的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$n \le k \le 10^6$$$) — 结果数组的长度和操作数。
第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 10^9, a_{i - 1} \ne a_i$$$) — 结果数组的元素。
保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^5$$$。
输出
对于每个测试用例,如果没有合适的长度为$$$k$$$的操作序列,则输出“NO“。否则,输出“是".
您可以输出“是“和”NO" 在任何情况下(例如,字符串 "是", "是的", "是“,和”是“将被识别为肯定答案)。
示例
输入复制
83 32 1 43 72 1 42 152 163 10256 32 13 289768 96 13 290768 96 15 75 1 6 3 104 66 8 5 10
输出复制
YES NO YES YES YES NO YES YES