仅由小写拉丁字母组成的字符串 $$$r$$$ 称为 通用 当且仅当 $$$r$$$ 按字典顺序小于 $$$r$$$ 的反转 $$$^{\text{†}}$$$。
给定一个字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。您需要赚取$$$s$$$ 通用。为此,您可以对 $$$s$$$ 执行以下操作 最多 $$$k$$$ 次:
- 选择两个索引 $$$i$$$ 和 $$$j$$$ ($$$1\le i,j\le n$$$),然后交换 $$$s_i$$$ 和 $$$s_j$$$。请注意,如果 $$$i=j$$$,则您什么都不做。
确定是否可以赚$$$s$$$ 通用 通过执行上述操作最多 $$$k$$$ 次。
$$$^{\text{*}}$$$字符串 $$$a$$$ 按字典顺序小于相同长度的字符串 $$$b$$$,当且仅当以下条件成立:
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中有一个字母比 $$$b$$$ 中的对应字母更早出现。
$$$^{\text{†}}$$$字符串的反转$$$r$$$是从右向左书写$$$r$$$得到的字符串。例如,字符串 $$$\texttt{abcad}$$$ 的反转为 $$$\texttt{dacba}$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1\le n\le 100$$$, $$$0\le k\le 10^4$$$) — 字符串 $$$s$$$ 的长度,以及可以执行的最大操作数。
第二行包含一个由 $$$n$$$ 小写拉丁字母组成的字符串 $$$s$$$。
输出
对于每个测试用例,打印“是“如果可以使$$$s$$$ 通用 最多执行 $$$k$$$ 次操作。否则,打印“NO".
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。
示例
输入复制
81 10000a3 3rev6 0string6 0theory9 2universal19 0codeforcesecrofedoc19 1codeforcesecrofedoc3 1zzz
输出复制
NO YES NO YES YES NO YES NO
注意
在第一个测试用例中,$$$s$$$ 在任何操作后都将保持不变。然而$$$\texttt{a}$$$反转后仍然是$$$\texttt{a}$$$,所以不可能使$$$s$$$ 通用.
在第二个测试用例中,字符串 $$$\texttt{rev}$$$ 按字典顺序小于 $$$\texttt{ver}$$$。因此,$$$s$$$ 已经 通用.
在第五个测试用例中,可以执行如下操作:
- 交换 $$$s_4$$$ 和 $$$s_7$$$。经过此操作,$$$s$$$ 变为 $$$\texttt{uniserval}$$$;
- 交换 $$$s_1$$$ 和 $$$s_3$$$。执行此操作后,$$$s$$$ 变为 $$$\texttt{inuserval}$$$。
字符串 $$$\texttt{inuserval}$$$ 是 通用.