Влад нашёл двоичную строку$$$^{\text{∗}}$$$ $$$s$$$ чётной длины $$$n$$$. Он считает пару индексов ($$$i, n - i + 1$$$), где $$$1 \le i \lt n - i + 1$$$ хорошей, если верно, что $$$s_i = s_{n - i + 1}$$$.
Например, в строке '010001' только $$$1$$$ хорошая пара, так как $$$s_1 \ne s_6$$$, $$$s_2 \ne s_5$$$ и $$$s_3=s_4$$$. А в строке '0101' нет ни одной хорошей пары.
Влад любит палиндромы, но не слишком сильно, поэтому он хочет переставить некоторые символы строки так, чтобы в строке оказалось ровно $$$k$$$ хороших пар индексов.
Определите, возможно ли переставить символы в данной строке так, чтобы ровно $$$k$$$ пар индексов ($$$i, n - i + 1$$$) были хорошими.
$$$^{\text{∗}}$$$Строка $$$s$$$ называется двоичной, если она состоит только из символов '0' и '1'
Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le \frac{n}{2}$$$, $$$n$$$ — чётное) — длину строки и нужное количество хороших пар.
Вторая строка каждого набора содержит двоичную строку $$$s$$$ длины $$$n$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите «YES», если существует способ переставить символы строки так, чтобы хороших пар стало ровно $$$k$$$, иначе выведите «{NO}».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
66 20000002 1014 1101110 2110101100110 111010110012 111
NO NO YES NO YES YES
| Codeforces Round 1027 (Div. 3) |
|---|
| Закончено |
