P11401 [Code+#8 初赛] 普勒亚

搬运自 [Code+ #8 初赛](https://gitlink.org.cn/thusaa/codeplus8pre)。

魔法少女小七得到了一个神奇的长度为 $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

第 $1$ 行，一个长度为 $n$ 的字符串 $s$。 第 $2$ 行，$n$ 个正整数表示对应的魔法值 $a_i$。

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

**【样例 #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$。 **【数据范围】** 对于 $20\%$ 的数据，$n \le 100$。 对于另外 $20\%$ 的数据，$n \le 5000$。 对于另外 $20\%$ 的数据，$s$ 中只有字符 `a`。 对于 $100\%$ 的数据，保证 $n \le 100,000$，$s$ 中只包含小写英文字母。