题目描述

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}, \color{blue}{4}, \color{blue}{4}, \color{violet}{2}, \color{blue}{4}]$。那么我们可以构造一条长度为 $6$ 的路径，由 $2$ 个区块组成：

$\color{red}{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$ 个区块的所有瓷砖颜色为 $\color{red}{\textbf{1}}$，第 $2$ 个区块的所有瓷砖颜色为 $\color{blue}{\textbf{4}}$。

在这个例子中，也可以构造一条长度为 $9$ 的路径，其中第 $1$ 个区块的颜色为 $\color{red}{\textbf{1}}$，第 $2$ 个区块的颜色为 $\color{green}{\textbf{3}}$，第 $3$ 个区块的颜色为 $\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 和 NO（例如 yEs、yes、Yes 和 YES 都会被识别为肯定回答）。

说明/提示

在第一个测试用例中，你可以直接从第一块瓷砖跳到最后一块瓷砖。

第二个测试用例的解释见题目描述。

由 ChatGPT 4.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

YES
YES
NO
NO
YES
YES
NO
YES
YES
YES