Magical Spell Power Calculation

Magical Girl Xiao Qi has obtained a magical string s of length \(n\) along with an array of magic values \(a_i\) for each position in the string. She can cast a spell using any substring of \(s\) of length \(l\). For a spell \(t\) of length \(l\), its magical power is defined as follows:

Find every occurrence of \(t\) in \(s\). For an occurrence ending at position \(pos_j\) (i.e. for all \(i\in[0,l)\), \(s_{pos_j-i} = t_{l-i}\)), take the magic value \(a_{pos_j}\). Form a sequence of these values in the order of increasing occurrence (i.e. from left to right). Then, the magical power of \(t\) is the number of prefix maximum elements in that sequence.

A value in a sequence \(W\) is called a prefix maximum if for index \(i\), \(W_i\) is strictly greater than every \(W_j\) for \(j < i\). For example, in the sequence \([2, 3, 1, 5]\), the prefix maximums are 2, 3, and 5.

Your task is: For each \(i\) from \(1\) to \(n\), compute the sum of magical powers for all distinct substrings of \(s\) of length \(i\) (two substrings are considered distinct if their contents differ). Output the \(n\) sums in order.

You will be rewarded with a happy magic if you succeed!

inputFormat

The input consists of three lines:

1. An integer \(n\) representing the length of the string.
2. A string \(s\) of length \(n\) consisting of lowercase letters.
3. \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) representing the magic values at each position.

outputFormat

Output a single line containing \(n\) space-separated integers. The \(i\)th integer is the sum of magical powers of all distinct substrings of \(s\) of length \(i\).

sample

3
abc
1 2 3

3 2 1