Description

半月的夜空中，寄托了多少人与人之间的思念啊

曦月知道，这些思念会汇集成一个字符串 $S$（$n = |S|$）。

由于思念汇集的过于复杂，因此曦月希望提炼出所有的思念。

我们定义 $Y_S(i)$ 表示对于字符串 $S$ 而言，长度为 $i$ 的子串中，字典序最小的，左端点最小的左端点的值

比如对于串 $S = \texttt{"baa"}$，$Y_S(1) = 2$、$Y_S(2) = 2$、$Y_S(3) = 1$。

曦月会告知你 $S$ 串，你只需要告诉曦月 $Y_S(i)$（$1 \le i \le n$）即可。

Input Format

第一行，两个参数，分别是 $\sigma \in \{10, 26, 10^7\}$ 和 $n$。

如果 $\sigma = 26$，那么第二行将是一个长为 $n$ 的小写字母字符串 $S$。

其他情况下，第二行将输入 $n$ 个位于 $[0, \sigma]$ 内的整数。

Output Format

输出一行，第 $i$ 个数表示 $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

数据范围的图不见了 QAQ

最大范围是 $1 \le n \le 3 \times {10}^5$。