У Поликарпа есть строка $$$s$$$ длины $$$n$$$, состоящая из строчных букв латинского алфавита.

Поликарп решил, что удалит из своей строки ровно $$$k$$$ букв. После удаления $$$k$$$ букв строка Поликарпа разделится на некоторое количество частей. Поликарп будет рассматривать только те части строки, в которых есть хотя бы одна буква, то есть пустые части рассматриваться не будут. Например, если $$$s = $$$ «abcdefghij» и Поликарп удалит первую, четвертую и шестую буквы, его строка разделится на три части «bc», «e» и «ghij».

Также Поликарп решил, что среди всех пар соседних букв он удалит не более одной буквы. Все $$$k$$$ удалений Поликарп произведет одновременно, то есть среди $$$k$$$ выбранных для удаления позиций не должно быть соседних позиций.

Поликарп хочет, чтобы все получившиеся части его строки были одинаковыми. Перед вами стоит задача определить, возможно ли удалить ровно $$$k$$$ букв из строки $$$s$$$, учитывая все описанные условия, так, чтобы желание Поликарпа исполнилось.