CF1893A.Anonymous Informant

You are given an array $b_1, b_2, \ldots, b_n$.

An anonymous informant has told you that the array $b$ was obtained as follows: initially, there existed an array $a_1, a_2, \ldots, a_n$, after which the following two-component operation was performed $k$ times:

1. A fixed point$^{\dagger}$ $x$ of the array $a$ was chosen.
2. Then, the array $a$ was cyclically shifted to the left$^{\ddagger}$ exactly $x$ times.

As a result of $k$ such operations, the array $b_1, b_2, \ldots, b_n$ was obtained. You want to check if the words of the anonymous informant can be true or if they are guaranteed to be false.

$^{\dagger}$A number $x$ is called a fixed point of the array $a_1, a_2, \ldots, a_n$ if $1 \leq x \leq n$ and $a_x = x$.

$^{\ddagger}$A cyclic left shift of the array $a_1, a_2, \ldots, a_n$ is the array $a_2, \ldots, a_n, a_1$.

给你一个数组 $b_1, b_2, \ldots, b_n$。

一位匿名线人告诉你：数组 $b$ 是通过如下方式得到的：最初存在一个数组 $a_1, a_2, \ldots, a_n$，然后对该数组重复执行以下两步操作共 $k$ 次：

1. 选择数组 $a$ 的一个不动点$^{\dagger}$ $x$；
2. 接着将数组 $a$ 向左循环移位$^{\ddagger}$ 恰好 $x$ 次。

经过 $k$ 次这样的操作后，得到了数组 $b_1, b_2, \ldots, b_n$。你想判断这位匿名线人的话是否可能为真，还是必然为假。

$^{\dagger}$ 若满足 $1 \leq x \leq n$ 且 $a_x = x$，则称数 $x$ 为数组 $a_1, a_2, \ldots, a_n$ 的一个不动点。

$^{\ddagger}$ 数组 $a_1, a_2, \ldots, a_n$ 的向左循环移位是指数组 $a_2, \ldots, a_n, a_1$。

Each test contains multiple test cases. The first line contains an 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, k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 10^9$) — the length of the array $b$ and the number of operations performed.

The second line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$) — the elements of the array $b$.

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

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output "Yes" if the words of the anonymous informant can be true, and "No" if they are guaranteed to be false.

对于每个测试用例，如果匿名线人的陈述可能为真，则输出“Yes”；如果其陈述必然为假，则输出“No”。

In the first test case, the array $a$ could be equal to $[3, 2, 3, 4, 3]$. In the first operation, a fixed point $x = 2$ was chosen, and after $2$ left shifts, the array became $[3, 4, 3, 3, 2]$. In the second operation, a fixed point $x = 3$ was chosen, and after $3$ left shifts, the array became $[3, 2, 3, 4, 3]$. In the third operation, a fixed point $x = 3$ was chosen again, and after $3$ left shifts, the array became $[4, 3, 3, 2, 3]$, which is equal to the array $b$.

In the second test case, the array $a$ could be equal to $[7, 2, 1]$. After the operation with a fixed point $x = 2$, the array became $[1, 7, 2]$. Then, after the operation with a fixed point $x = 1$, the array returned to its initial state $[7, 2, 1]$. These same $2$ operations (with $x = 2$, and $x = 1$) were repeated $49$ times. So, after $100$ operations, the array returned to $[7, 2, 1]$.

In the third test case, it can be shown that there is no solution.

在第一个测试用例中，数组 $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]$。

在第三个测试用例中，可以证明不存在满足条件的解。