В задачах на строки часто требуется найти строку, обладающую какими-то особыми свойствами. Авторам задачи снова было лень придумывать название для такой строки, поэтому они назвали ее хорошей.
Строка называется хорошей, если она содержит ровно k различных символов. В виде конкатенации какого наименьшего количества хороших строк можно представить данную строку s?
В первой строке содержится целое число k (1 ≤ k ≤ 26).
Во второй строке содержится строка s (1 ≤ |s| ≤ 200000), состоящая из строчных латинских символов.
Выведите через пробел наименьшее количество хороших строк, на которые можно разбить каждый префикс строки s, начиная с префикса, состоящего из первого символа строки, и заканчивая префиксом, совпадающим со строкой. Ведь так тщательнее протестируется, правда?
Если для какого-либо префикса разбиение невозможно, выведите для него «-1».
2
abacaba
-1 1 1 2 2 3 3
