Мюллер давно подозревал, что Штирлиц периодически отсылает шифровки в СССР. И вот, наконец, он почти поймал его за руку: роясь в бумагах Штирлица, он нашёл непонятный набор цифр, записанный на чистом листе. Сразу догадавшись, что это шифровка, он вызвал Штирлица на допрос. Тот же невозмутимо объяснил, что это всего лишь номер лотерейного билета, который он переписал на лист бумаги, чтобы не забыть. Штирлиц никогда не был так близок к провалу — ведь на листе были записаны координаты бункера Гитлера.

Для передачи этих данных в Центр Штирлиц использовал следующий алгоритм:

• На вход подаётся строка s = s₁s₂…s_n.
• Выбирается ключ k — целое положительное число, строго меньшее n.
• Для каждого символа строки s_i выполняется следующая процедура:
  1. Рассматривается строка q_i, состоящая из k подряд идущих символов строки s, начиная с i-го: q_i = s_is_i + 1…s_{i + k − 1}. Если до конца строки не набирается k символов, то оставшиеся символы берутся из начала строки: q_i = s_i…s_ns₁…s_{i + k − 1 − n}.
  2. Для строки q_i подсчитывается количество различных непустых её подстрок — m_i.
• Последовательность m₁, m₂, …, m_n выдаётся в качестве ответа.

Шифровать этим алгоритмом не так уж просто, а как потом это расшифровывать, вообще известно только советской разведке. Вам предоставляется шанс на несколько минут почувствовать себя Штирлицем.

В первой строке записан ключ k, 1 ≤ k ≤ 1000. Вторая строка содержит строку s, которую вам предстоит зашифровать. Строка состоит из строчных латинских букв, её длина строго больше k и не превосходит 4000.

Выведите числа m₁, m₂, …, m_n, разделённые пробелами.