A. Анонимный информатор
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$b_1, b_2, \ldots, b_n$$$.

Некий анонимный информатор сообщил вам, что массив $$$b$$$ был получен следующим образом: изначально существовал некоторый массив $$$a_1, a_2, \ldots, a_n$$$, после чего $$$k$$$ раз была произведена следующая двухкомпонентная операция:

  1. Была выбрана некоторая фиксированная точка$$$^{\dagger}$$$ массива $$$a$$$, пусть $$$x$$$.
  2. После чего ровно $$$x$$$ раз массив $$$a$$$ был заменён на свой циклический сдвиг влево$$$^{\ddagger}$$$.

И в результате $$$k$$$ таких операций был получен массив $$$b_1, b_2, \ldots, b_n$$$. Вы хотите проверить, могут ли слова анонимного информатора быть правдивы, или же он гарантированно лжёт.

$$$^{\dagger}$$$Число $$$x$$$ называется фиксированной точкой массива $$$a_1, a_2, \ldots, a_n$$$, если $$$1 \leq x \leq n$$$ и $$$a_x = x$$$.

$$$^{\ddagger}$$$Циклический сдвиг влево от массива $$$a_1, a_2, \ldots, a_n$$$ это массив $$$a_2, \ldots, a_n, a_1$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целые числа $$$n, k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 10^9$$$) — длину массива $$$b$$$ и количество проведённых операций.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — элементы массива $$$b$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «Yes», если слова анонимного информатора могут быть правдой, и «No», если он гарантированно лжёт.

Пример
Входные данные
6
5 3
4 3 3 2 3
3 100
7 2 1
5 5
6 1 1 1 1
1 1000000000
1
8 48
9 10 11 12 13 14 15 8
2 1
1 42
Выходные данные
Yes
Yes
No
Yes
Yes
No
Примечание

В первом наборе входных данных массив $$$a$$$ мог быть равен $$$[3, 2, 3, 4, 3]$$$. В первой операции была выбрана фиксированная точка $$$x = 2$$$, и после $$$2$$$ сдвигов влево массив принял вид $$$[3, 4, 3, 3, 2]$$$. Во второй операции была выбрана фиксированная точка $$$x = 3$$$, и после $$$3$$$ сдвигов влево массив принял вид $$$[3, 2, 3, 4, 3]$$$. В третьей же операции была выбрана фиксированная точка $$$x = 3$$$, и после $$$3$$$ сдвигов влево массив принял вид $$$[4, 3, 3, 2, 3]$$$, чему и равняется массив $$$b$$$.

Во втором наборе входных данных массив $$$a$$$ мог быть равен $$$[7, 2, 1]$$$. После операции с фиксированной точкой $$$x = 2$$$ массив принял вид $$$[1, 7, 2]$$$. Далее после операции с фиксированной точкой $$$x = 1$$$ массив снова принял изначальный вид $$$[7, 2, 1]$$$. Далее эти же $$$2$$$ операции (с $$$x = 2$$$ и $$$x = 1$$$) были повторены $$$49$$$ раз. И итого после $$$100$$$ операций массив снова принял вид $$$[7, 2, 1]$$$.

В третьем наборе входных данных нетрудно показать, что ответа нет.