背景

搬运自 Code+ #8 初赛。

题目描述

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

ababa
5 2 3 4 1

3 3 2 2 1

aaaa
3 2 3 4

2 3 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$。

【数据范围】

对于 $20\%$ 的数据，$n \le 100$。

对于另外 $20\%$ 的数据，$n \le 5000$。

对于另外 $20\%$ 的数据，$s$ 中只有字符 a。

对于 $100\%$ 的数据，保证 $n \le 100,000$，$s$ 中只包含小写英文字母。