仰望半月的夜空

“你不久也会遇到喜欢的女生吧。听好了，你可得好好守护她喔。” 这是父亲给予戎崎裕一的教诲 父亲称不上是一个合格的父亲 但是，却正是这样的父亲，连接了戎崎裕一和秋庭里香  秋庭里香，明明是那样的傲娇，却不得不去守护的女生 但同时，又是一个为了回忆，为了懵懂的爱情而坚强着的女生 你是不是在她身上看到了小夜子的身影呢？夏目吾郎医生 你是不是在他身上看到了过去的自己呢？夏目吾郎医生 也许疾病切断了人与人之间的联系，但是曾经存在的痕迹，定将会化作美好的回忆，流传下去 愿你们幸福

半月的夜空中，寄托了多少人与人之间的思念啊 曦月知道，这些思念会汇集成一个字符串 $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$）即可。

第一行，两个参数，分别是 $\sigma \in \{10, 26, 10^7\}$ 和 $n$。 如果 $\sigma = 26$，那么第二行将是一个长为 $n$ 的小写字母字符串 $S$。 其他情况下，第二行将输入 $n$ 个位于 $[0, \sigma]$ 内的整数。

输出一行，第 $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

数据范围的图不见了 QAQ 最大范围是 $1 \le n \le 3 \times {10}^5$。