Vlad 记得他有一系列 $$$n$$$ 瓷砖和一个数字 $$$k$$$。这些图块从左到右编号,第 $$$i$$$ 个图块的颜色为 $$$c_i$$$。
如果你站在第一块瓷砖上并开始向右跳跃任意数量的瓷砖,你可以获得一条长度为 $$$p$$$ 的路径。路径的长度就是你所站的砖块的数量。
Vlad 想看看是否可以获得长度为 $$$p$$$ 的路径,使得:
- 它以索引 $$$n$$$ 的图块结束;
- $$$p$$$ 可以被 $$$k$$$ 整除
- 路径被分成每个长度恰好 $$$k$$$ 的块;
- 每个块中的图块具有相同的颜色,相邻块中的颜色不一定不同。
例如,令 $$$n = 14$$$,$$$k = 3$$$。
方块的颜色包含在数组 $$$c$$$ = [$$$\color{red}{1}, \color{violet}{2}, \color{red}{1}, \color{red}{1}, \color{gray}{7}, \color{orange}{5}, \color{green}{3}, \color{green}{3}, \color{red}{1}, \color{green}{3}, \颜色{蓝色}{4}、\颜色{蓝色}{4}、\颜色{紫色}{2}、\颜色{蓝色}{4}$$$]。然后我们可以构造一条长度为 $$$6$$$ 的路径,由 $$$2$$$ 块组成:
$$$\color{红色}{c_1} \rightarrow \color{red}{c_3} \rightarrow \color{red}{c_4} \rightarrow \color{blue}{c_{11}} \rightarrow \color{blue}{c_{12}} \rightarrow \color{blue}{c_{14}}$$$
$$$1$$$-st 块中的所有图块将具有颜色 $$$\color{red}{\textbf{1}}$$$,$$$2$$$-nd 块中的所有图块将具有颜色 $$$\color{blue}{\textbf{4}}$$$。
在此示例中,还可以构建长度为 $$$9$$$ 的路径,其中来自 $$$1$$$-st 块的所有图块将具有颜色 $$$\color{red}{\textbf{1}}$$$,来自 $$$2$$$-nd 块的所有图块将具有颜色 $$$\color{green}{\textbf{3}}$$$,来自 $$$\color{green}{\textbf{3}}$$$ $$$3$$$-rd 块的颜色为 $$$\color{blue}{\textbf{4}}$$$。
输入
输入数据的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) - 系列中的图块数量和块的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — 方块的颜色。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上输出:
- 如果您可以获得满足这些条件的路径,则为“是”;
- 否则不。
任何情况下都可以输出 YES 和 NO(例如,字符串 yEs、yes、Yes 和 YES 将被识别为肯定响应)。
示例
输入 #1
10 4 2 1 1 1 1 14 3 1 2 1 1 7 5 3 3 1 3 4 4 2 4 3 3 3 1 3 10 4 1 2 1 2 1 2 1 2 1 2 6 2 1 3 4 1 6 6 2 2 1 1 4 2 2 1 1 1 2 1 1 2 3 2 2 2 2 4 1 1 1 2 2
输出 #1
YES YES NO NO YES YES NO YES YES YES
注意
在第一个测试用例中,您可以从第一个图块跳转到最后一个图块;
第二个测试用例在问题陈述中进行了解释。