A. Сервал и теория строк
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Строка $$$r$$$, состоящая только из строчных латинских букв, называется вселенской, если и только если $$$r$$$ лексикографически меньше$$$^{\text{∗}}$$$ развёрнутой$$$^{\text{†}}$$$ строки $$$r$$$.

Вам дана строка $$$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$$$ и максимальное количество операций, которые вы можете выполнить.

Вторая строка содержит строку $$$s$$$, состоящую из $$$n$$$ строчных латинских букв.

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

Для каждого набора входных данных выведите «YES», если возможно сделать $$$s$$$ вселенской, выполнив операцию не более $$$k$$$ раз. Иначе выведите «NO».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
8
1 10000
a
3 3
rev
6 0
string
6 0
theory
9 2
universal
19 0
codeforcesecrofedoc
19 1
codeforcesecrofedoc
3 1
zzz
Выходные данные
NO
YES
NO
YES
YES
NO
YES
NO
Примечание

В первом наборе входных данных строка $$$s$$$ останется неизменной после любых операций. Однако обратная строка для $$$\texttt{a}$$$ равна $$$\texttt{a}$$$, поэтому сделать строку $$$s$$$ вселенской невозможно.

Во втором наборе входных данных строка $$$\texttt{rev}$$$ лексикографически меньше, чем $$$\texttt{ver}$$$. Таким образом, строка $$$s$$$ уже вселенская.

В пятом наборе входных данных вы можете выполнить операции следующим образом:

  1. Поменяйте местами $$$s_4$$$ и $$$s_7$$$. После этой операции строка $$$s$$$ станет $$$\texttt{uniserval}$$$;
  2. Поменяйте местами $$$s_1$$$ и $$$s_3$$$. После этой операции строка $$$s$$$ станет $$$\texttt{inuserval}$$$.

И строка $$$\texttt{inuserval}$$$ является вселенской.