Cocktail Party

You are given a string of length $n$ with the labels of $n$ cups of cocktail. The $i$-th cup has label $s_i$, and every label is one of the 26 lowercase English letters. Let $\mathrm{Str}(l,r) = s_l s_{l+1} \cdots s_r$ be the string formed by the labels from cup $l$ to cup $r$. If $\mathrm{Str}(p,p_0) = \mathrm{Str}(q,q_0)$ where $1 \le p \le p_0 \le n$, $1 \le q \le q_0 \le n$, $p \ne q$, and $p_0-p+1 = q_0-q+1 = r$, then cup $p$ and cup $q$ are called $r$-similar. If two cups are $r$-similar for some $r > 1$, they are also $1$-similar, $2$-similar, ..., and $(r-1)$-similar. For any $1 \le p \le q \le n$ with $p \ne q$, cups $p$ and $q$ are $0$-similar.

Freda assigns a deliciousness value $a_i$ to each cup. Mixing cup $p$ and cup $q$ produces a cocktail with deliciousness $a_p a_q$. For each $r = 0, \dots, n-1$, the problem asks how many pairs of cups are $r$-similar, and the maximum deliciousness obtainable by mixing two $r$-similar cups.

The first line contains an integer $n$, the number of cups. The second line contains a string $S$ of length $n$, where the $i$-th character is the label of cup $i$. The third line contains $n$ integers separated by single spaces, where the $i$-th integer is $a_i$.

Print $n$ lines. The $i$-th line contains two integers: the number of pairs of $(i-1)$-similar cups, and the maximum deliciousness from mixing two $(i-1)$-similar cups. If no two cups are $(i-1)$-similar, print 0 0 on that line.

$10 \le n \le 300\,000$

$|a_i| \le 1\,000\,000\,000$