C. Плитки возвращаются
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Влад вспомнил, что у него был ряд из $$$n$$$ плиток и число $$$k$$$. Плитки пронумерованы слева направо, и $$$i$$$-я плитка имеет цвет $$$c_i$$$.

Если встать на первую плитку и начать прыгать на любое количество плиток вправо, можно получить путь длины $$$p$$$. Длиной пути называется количество плиток, на которых вы стояли.

Влад хочет понять, можно ли получить путь длины $$$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$$$-x блоков:

$$$\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», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
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
Примечание

В первом наборе входных данных можно прыгнуть с первой плитки на последнюю;

Второй набор входных данных разобран в условии задачи.