Description

In the half-moon night sky, how many people’s feelings for each other are carried.

Xiyue knows that these feelings will gather into a string $S$ ($n = |S|$).

Because the feelings are gathered in a way that is too complex, Xiyue hopes to refine all of them.

We define $Y_S(i)$ as follows: for the string $S$, among all substrings of length $i$, take the lexicographically smallest one; if there are multiple, take the one with the smallest left endpoint. Then $Y_S(i)$ is the value of that left endpoint.

For example, for $S = \texttt{"baa"}$, $Y_S(1) = 2$, $Y_S(2) = 2$, $Y_S(3) = 1$.

Xiyue will tell you the string $S$. You only need to tell Xiyue $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$, then the second line is a lowercase letter string $S$ of length $n$.

Otherwise, the second line contains $n$ integers in $[0, \sigma]$.

Output Format

Output one line. The $i$-th number表示 the value of $Y_S(i)$.

26 11
remoonqaqac

8 10 8 8 2 2 2 2 2 2 1

26 11
txdydkwqaqa

9 9 9 5 5 5 5 3 3 1 1

10000000 17
9 9 8 2 4 4 3 5 3 1 9 2 6 0 8 1 7

14 14 14 14 10 10 10 10 4 4 4 4 4 4 3 2 1

Hint

The Constraints chart is missing QAQ.

The maximum range is $1 \le n \le 3 \times {10}^5$.

Translated by ChatGPT 5