由于粉免和兔子是不可区分的，粉免可以在粉兔的队伍中跑来跑去。更可怕的是，免子是一种量子生物，它们的质量是测不准的！这严重干扰了你的计划。

幸运的是，你想起粉兔经常在网上搜索一些有关自己大作业的事情，而粉免则只会上 arXiv。聪明的你想起可以用这一点来区分。

具体来说，对于一个搜索内容，我们用字符串 $S$ 来表示它。令 $g(S)$ 为字典序比较意义下 $S$ 的最大后缀。当粉兔认为自己的搜索内容不合适的时候，就会令 $S$ 变为 $S$ 拼接上 $g(S)$ 形成的字符串，表示对 $S$ 中重要的部分进行强调，然后再搜一次。粉兔会重复这一搜索过程，直到满意为止。

如果一只兔子（免子）是粉兔的话，它应该对这样的搜索方式非常熟练，那么数出一条搜索记录中每种字符的出现次数也不再话下。

由于你只是一只拥有计算机的跳蚤，你当然需要写一个程序来确保粉兔给出的答案是对的：假设粉兔对搜索内容连续进行了 $k$ 次强调，那么你要给出每种字符在最后的搜索记录中出现了几次。由于这个次数太大，需要对 $998244353$ 取模。

形式化题意：

对一个字符串 $S$ 定义操作 $f(S)=S+g(S)$，其中 $+$ 为字符串拼接，$g(S)$ 为字典序比较意义下 $S$ 的最大后缀。

求 $f^k(S)$ 中每种字符的出现次数对 $998244353$ 取模，其中 $f^k(S)=f(f^{k-1}(S)),f^0(S)=S$。

输入格式：

第一行，一个仅包含小写字母的字符串 $S$。

第二行，一个整数 $k$。

输出格式：

一行，共 $26$ 个整数 $c_a,\ldots,c_z$，按字母表顺序表示每种小写字母出现次数模 $998244353$。

样例一

input

aacbc
2

output

2 3 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

explanation

$S=\texttt{aacbc},\ f(S)=\texttt{aacbccbc},\ f^2(S)=f(f(S))=\texttt{aacbccbcccbc}$。

样例二

见附件下载。该样例满足子任务 2 的限制。

样例三

见附件下载。该样例满足子任务 3 的限制。

样例四

见附件下载。该样例满足子任务 5 的限制。

数据范围：

对于 $100\%$ 的数据：$1\leq |S|\leq 6\times 10^5,\ 1\leq k\leq 10^9$，字符串 $S$ 仅包含小写字母。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$