小J是一位勤奋的大学生，在清华大学计算机系学习的他，每天都会遇到不少有挑战性的问题。
今天，小J的老师在课上讲了一个字符串的加密算法，对于一个长度为N的字符串，我们在字符串的末尾添加一个特殊的字符“.”。之后将字符串试作一个环，从位置1,2,3,...,N+1为起点读出N+1个字符，就能得到N+1个字符串。比如对于字符串“ABCAAA”，我们可以得到这N+1个串:

ABCAAA.
BCAAA.A
CAAA.AB
AAA.ABC
AA.ABCA
A.ABCAA
.ABCAAA

接着我们对得到的这N+1个串按字典序从小到大进行排序(注意特殊字符“.”的字典序小于任何其它的字符)结果如下:

.ABCAAA
A.ABCAA
AA.ABCA
AAA.ABC
ABCAAA.
BCAAA.A
CAAA.AB

最后，将排序后的N+1个串的最后一个字符取出，按照顺序排成一个新的字符串，也就是上面这个表的最后一列，就是加密后的密文“AAAC.AB”。
聪明的小J很快就理解了加密算法，然而因为课堂的时间有限，老师没有来得及讲解密算法就下课了。好奇的小J很想知道如何对字符串进行解密，即通过加密后的密文求出加密前的字符串。你能帮他解决这个问题吗？

第一行有两个整数N,M，分别表示加密前的字符串长度和字符集的大小，其中字符用整数1,2,3,...,M编号，添加的特殊字符“.”用0编号。
第二行为N+1个整数，表示加密后的字符串。

输出仅一行，包含N个整数，用空格隔开，依次表示加密前字符串中每个字符的编号。

【样例说明】
将样例输入与输出中的1,2,3分别视为A,B,C,则样例即为题目描述所述的字符串
【数据规模】
N≤200000，M≤200000