Magical Girl Xiaoqi has obtained a magical string $s$ of length $n$, where each position $i$ has an associated magic value $a_i$. She can use a substring of length $l$ as a spell. For a spell $t$ of length $l$, its magic power is defined as the number of prefix maximums in the sequence formed by the magic values $a_{pos_j}$ of the right endpoints $pos_j$ of every occurrence of $t$ in $s$ (i.e., for all $i \in [0, l)$, $s_{pos_j-i} = t_{l-i}$), ordered from left to right.

For each $i \in [1, n]$, Xiaoqi wants to know the sum of the magic power of all spells of length $i$ in $s$ (two spells are considered different if and only if their string contents are different). Can you help her? She will give you a "happy magic" as a reward!

Prefix maximum: For a sequence $W$, $W_i$ is a prefix maximum if and only if $W_j < W_i$ for all $j < i$.

Input

The first line contains a string $s$ of length $n$.

The second line contains $n$ positive integers representing the corresponding magic values $a_i$.

Output

Output a single line containing $n$ positive integers, where the $i$-th number represents the sum of the magic power of all spells of length $i$.

Examples

Input 1

ababa
5 2 3 4 1

Output 1

3 3 2 2 1

Note 1

For length $1$, the substrings are a and b, forming sequences 5 3 1 and 2 4 respectively, with prefix maximum counts of $1$ and $2$.

For length $2$, the substrings are ab and ba, forming sequences 2 4 and 3 1 respectively, with prefix maximum counts of $2$ and $1$.

For length $3$, the substrings are aba and bab, forming sequences 3 1 and 4 respectively, with prefix maximum counts of $1$ and $1$.

For length $4$, the substrings are abab and baba, forming sequences 4 and 1 respectively, with prefix maximum counts of $1$ and $1$.

For length $5$, the substring is ababa, forming sequence 1, with a prefix maximum count of $1$.

Input 2

aaaa
3 2 3 4

Output 2

2 3 2 1

Subtasks

For $20\%$ of the data, $n \leq 100$.

For another $20\%$ of the data, $n \leq 5\,000$.

For another $20\%$ of the data, $s$ consists entirely of the character a.

For $100\%$ of the data, $n \leq 10^5$, $a_i \leq 10^9$, and $s$ consists of lowercase English letters.