魔法少女小七得到了一个神奇的长度为 $n$ 的字符串 $s$，每个位置对应有一个魔法值 $a_i$。每次她可以使用一个长度为 $l$ 的子串作为咒语。对于长度为 $l$ 的咒语 $t$，它的魔力是它在 $s$ 中出现的每个位置的右端点 $pos_j$ （即$\forall i \in [0,l),\ s_{pos_j-i}=t_{l-i}$）的魔法值 $a_{pos_j}$ 从左往右连成的序列的前缀最大值个数。

对于每个 $i \in [1,n]$，小七想知道 $s$ 中所有长度为 $i$ 的咒语（两个咒语不同当且仅当其对应的字符串内容不同）的魔力之和。你能帮帮她吗？她会给你一个开心魔法作为报酬！

前缀最大值：对于序列$W$来说$W_i$是前缀最大值当且仅当对于任何$j < i$都有$W_j < W_i$。

输入格式

第 $1$ 行，一个长度为 $n$ 的字符串 $s$。

第 $2$ 行，$n$ 个正整数表示对应的魔法值 $a_i$。

输出格式

输出 $1$ 行 $n$ 个正整数，第 $i$ 个数表示长度为 $i$ 的咒语的魔法值之和。

样例数据

样例 1 输入

ababa
5 2 3 4 1

样例 1 输出

3 3 2 2 1

样例 1 解释

长度为 $1$ 的子串有 a和 b 两种，分别构成序列 5 3 1 和 2 4，各自的前缀最大值个数为 $1$ 和 $2$。

长度为 $2$ 的子串有 ab 和 ba 两种，分别构成序列 2 4 和 3 1，各自的前缀最大值个数为 $2$ 和 $1$。

长度为 $3$ 的子串有 aba 和 bab 两种，构成序列 3 1 和 4，各自的前缀最大值个数为 $1$ 和 $1$。

长度为 $4$ 的子串有 abab 和 baba 两种，构成序列 4 和 1 ，各自的前缀最大值个数为 $1$ 和 $1$。

长度为 $5$ 的子串有 ababa 一种，构成序列 1，前缀最大值个数为 $1$。

样例 2 输入

aaaa
3 2 3 4

样例 2 输出

2 3 2 1

子任务

对于 $20\%$ 的数据，保证 $n \leq 100$ 。

对于另外 $20\%$ 的数据，保证 $n\leq 5\,000$。

对于另外 $20\%$ 的数据，保证 $S$ 全部由 a 构成。

对于 $100\%$ 的数据，保证 $n \leq 10^5,\ a_i\le 10^9$ ，保证 $S$ 由小写英文字母组成。