ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural Championship 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

G. Cipher Message 2

Time limit: 3.0 second
Memory limit: 64 MB
Müller had been suspecting for a long time that Stierlitz had been sending cipher messages to the USSR from time to time. And now Müller almost got the proof of that. Rummaging through Stierlitz's papers, he found a strange sequence of digits written on a clean sheet of paper. He guessed that it was a cipher message and called Stierlitz for questioning. But Stierlitz calmly answered that the digits were the number of a lottery-ticket that he had written in order not to forget it. Stierlitz had never been so close to a failure: there were the coordinates of Hitler's bunker on the sheet.
For transmitting the data to the center, Stierlitz used the following algorithm:
  • The input is a string s = s1s2sn.
  • A key k is chosen; it is a positive integer smaller than n.
  • For every symbol si of the string, the following procedure is applied:
    1. The string qi is considered consisting of k consecutive symbols of the string s starting from the ith: qi = sisi + 1si + k − 1. If there are less than k symbols till the end of the string, then the remaining symbols are taken from the beginning of the string: qi = sisns1si + k − 1 − n.
    2. For the string qi, the number of its different nonempty substrings mi is calculated.
  • The sequence m1, m2, …, mn is the output of the algorithm.
It is not easy to cipher with this algorithm, and how to decode the messages only the Soviet intelligence service knows. You are given a chance to feel yourself the famous Stierlitz for several minutes.


In the first line you are given the key k, 1 ≤ k ≤ 1000. The second line contains the string s you are supposed to cipher. The string consists of lowercase English letters, and its length is strictly greater than k and does not exceed 4000.


Output the numbers m1, m2, …, mn separated with spaces.


5 6 5 3 5 6
Problem Author: Dmitry Ivankov
Problem Source: The 13th Urals Collegiate Programing Championship, April 04, 2009
To submit the solution for this problem go to the Problem set: 1706. Cipher Message 2