题目描述
Background
"You'll soon meet a girl you like. Remember, you must protect her well."
These were the teachings given to Yuichi by his father.
His father was not the ideal father,
Yet it was this very father who connected Yuichi with Rika.
Rika, who was so tsundere, yet a girl who had to be protected,
And at the same time, a girl who was strong for the sake of memories and naive love.
Do you see the shadow of Sayoko in her? Dr. Natsume
Do you see your past self in him? Dr. Natsume
Perhaps illness has severed the connections between people, but the traces that once existed will surely turn into beautiful memories and be passed down.
May you be happy.
Problem Description
In the half-moon sky, how many thoughts between people are寄托!
Xiyue knows that these thoughts will gather into a string $S$ ($n = |S|$).
Due to the complexity of the gathered thoughts, Xiyue wishes to refine all of them.
We define $Y_S(i)$ as the value of the leftmost endpoint of the lexicographically smallest substring of length $i$ in string $S$.
For example, for the string $S = \texttt{"baa"}$, $Y_S(1) = 2$, $Y_S(2) = 2$, $Y_S(3) = 1$.
Xiyue will provide you with the string $S$, and you only need to tell Xiyue the values of $Y_S(i)$ ($1 \le i \le n$).
Input Format
The first line contains two parameters, $\sigma \in \{10, 26, 10^7\}$ and $n$.
If $\sigma = 26$, the second line will be a string $S$ of length $n$ consisting of lowercase letters.
In other cases, the second line will input $n$ integers within the range $[0, \sigma]$.
Output Format
Output one line, where the $i$-th number represents the value of $Y_S(i)$.
Sample Input and Output
Sample Input #1
26 11
remoonqaqac
Sample Output #1
8 10 8 8 2 2 2 2 2 2 1
Sample Input #2
26 11
txdydkwqaqa
Sample Output #2
9 9 9 5 5 5 5 3 3 1 1
Sample Input #3
10000000 17
9 9 8 2 4 4 3 5 3 1 9 2 6 0 8 1 7
Sample Output #3
14 14 14 14 10 10 10 10 4 4 4 4 4 4 3 2 1
Notes
The diagram for the data range is missing QAQ
The maximum range is $1 \le n \le 3 \times 10^5$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分