P5108 Half-Moon Night Sky

“You will soon meet a girl you like. Listen carefully, you must protect her well.” This was the advice that Father gave to Yuichi Ronzaki. Father could hardly be called a qualified father. But it was exactly such a father who connected Yuichi Ronzaki and Rika Akiba.  Rika Akiba is a girl who is clearly a tsundere, yet someone you cannot help but protect. At the same time, she is also a girl who stays strong for memories, and for innocent love. Do you see Sayoko’s shadow in her, Doctor Goro Natsume? Do you see your past self in him, Doctor Goro Natsume? Maybe illness cuts off the connection between people, but the traces that once existed will surely turn into beautiful memories and be passed on. May you be happy.

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$).

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 one line. The $i$-th number表示 the value of $Y_S(i)$.

The Constraints chart is missing QAQ. The maximum range is $1 \le n \le 3 \times {10}^5$. Translated by ChatGPT 5