Medal Redemption LCS Counting

In the NOI festival, XiaoDou participates in a fun fair. Every time he completes an event, he is awarded a medal. Each medal bears only one of the letters N, O, or I. XiaoDou has collected a string of K medals (the medal string). In order to redeem a prize, he needs to choose a redemption string of length N consisting of the letters N, O, and I with an additional constraint that the substring NOI (i.e. N followed immediately by O then I) does not appear in it.

The reward level is determined as the length of the longest common subsequence (LCS) between the medal string and the redemption string. XiaoDou is curious: for each possible reward level, how many different valid redemption strings produce that level?

You are given two numbers: K (the length of the medal string) and N (the length of the redemption string), and the medal string itself (of length K). Output the counts for each reward level from 0 up to min(K, N) (inclusive), separated by spaces.

Note: If a redemption string contains the substring NOI (with the letters consecutive in that order), it is considered invalid.

The LCS between two strings is defined in the usual way. All formulas below are in LaTeX format. For example, the medal string is denoted by $S$ (of length $K$) and the redemption string by $T$ (of length $N$), and the reward level is $\mathrm{LCS}(S,T)$.

inputFormat

The input consists of two lines. The first line contains two integers K and N separated by spaces. The second line contains the medal string S of length K (each character is either N, O, or I).

outputFormat

Output min(K, N)+1 integers separated by a space. The i-th number (starting from i = 0) represents the number of valid redemption strings for which the LCS with S is exactly i.

sample

2 2
NO

1 7 1