310557: CF1851C. Tiles Comeback

C. Tiles Comebacktime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Vlad remembered that he had a series of $n$ tiles and a number $k$. The tiles were numbered from left to right, and the $i$-th tile had colour $c_i$.

If you stand on the first tile and start jumping any number of tiles right, you can get a path of length $p$. The length of the path is the number of tiles you stood on.

Vlad wants to see if it is possible to get a path of length $p$ such that:

• it ends at tile with index $n$;
• $p$ is divisible by $k$
• the path is divided into blocks of length exactly $k$ each;
• tiles in each block have the same colour, the colors in adjacent blocks are not necessarily different.

For example, let $n = 14$, $k = 3$.

The colours of the tiles are contained in the array $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}$]. Then we can construct a path of length $6$ consisting of $2$ blocks:

$\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}}$

All tiles from the $1$-st block will have colour $\color{red}{\textbf{1}}$, from the $2$-nd block will have colour $\color{blue}{\textbf{4}}$.

It is also possible to construct a path of length $9$ in this example, in which all tiles from the $1$-st block will have colour $\color{red}{\textbf{1}}$, from the $2$-nd block will have colour $\color{green}{\textbf{3}}$, and from the $3$-rd block will have colour $\color{blue}{\textbf{4}}$.

Input

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$)—the number of tiles in the series and the length of the block.

The second line of each test case contains $n$ integers $c_1, c_2, c_3, \dots, c_n$ ($1 \le c_i \le n$) — the colours of the tiles.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output on a separate line:

• YES if you can get a path that satisfies these conditions;
• NO otherwise.

You can output YES and NO in any case (for example, strings yEs, yes, Yes and YES will be recognized as positive response).

ExampleInput

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

Output

YES
YES
NO
NO
YES
YES
NO
YES
YES
YES

Note

In the first test case, you can jump from the first tile to the last tile;

The second test case is explained in the problem statement.

**题目大意：**

Vlad 记得他有一系列 $ n $ 块瓦片和一个数字 $ k $。瓦片从左到右编号，第 $ i $ 块瓦片的颜色为 $ c_i $。

如果你站在**第一块**瓦片上，开始向**右**跳任意数量的瓦片，你可以得到一条长度为 $ p $ 的路径。路径的长度是你站过的瓦片数量。

Vlad 想知道是否有可能得到一条长度为 $ p $ 的路径，使得：

- 路径以编号为 $ n $ 的瓦片结束；
- $ p $ 能被 $ k $ 整除；
- 路径被划分为每个长度正好为 $ k $ 的块；
- 每块中的瓦片颜色相同，相邻块的颜色不一定要不同。

**输入数据格式：**

输入数据的第一行包含一个整数 $ 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**。**题目大意：** Vlad 记得他有一系列 $ n $ 块瓦片和一个数字 $ k $。瓦片从左到右编号，第 $ i $ 块瓦片的颜色为 $ c_i $。 如果你站在**第一块**瓦片上，开始向**右**跳任意数量的瓦片，你可以得到一条长度为 $ p $ 的路径。路径的长度是你站过的瓦片数量。 Vlad 想知道是否有可能得到一条长度为 $ p $ 的路径，使得： - 路径以编号为 $ n $ 的瓦片结束； - $ p $ 能被 $ k $ 整除； - 路径被划分为每个长度正好为 $ k $ 的块； - 每块中的瓦片颜色相同，相邻块的颜色不一定要不同。 **输入数据格式：** 输入数据的第一行包含一个整数 $ 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**。