You are given a string of length $n$ representing the labels of $n$ cups of cocktail. The $i$-th cup of cocktail has label $s_i$, and the labels are among 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 of the cocktails from the $l$-th cup to the $r$-th cup. 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$, $p_0-p+1=q_0-q+1=r$, we say the $p$-th cup of cocktail and $q$-th cup of cocktail are $r$-similar. Of course, for two cups of cocktail that are $r$-similar ($r>1$) they are also 1-similar, 2-similar, ..., and $(r-1)$-similar. In particular, for any $1\le p\le q\le n,p\ne q$, the $p$-th cup of cocktail and $q$-th cup of cocktail are $0$-similar.

Freda assigns the "deliciousness" for each cup of cocktail, and the $i$-th cup has deliciousness $a_i$. If we mix $p$-th cup of cocktail and $q$-th cup of cocktail, we may obtain cocktail with deliciousness $a_p{a}_q$. The problem asks for each $r=0,\dots ,n-1$, how many ways we may select two cups of cocktail that are $r$-similar, and compute the maximum possible deliciousness by mixing two cups of cocktail that are $r$-similar.

Input Specification

The first line of the input contains an integer $n$ denoting the number of cups of cocktail. The second line contains a string $S$ with length $n$ such that the $i$-th character denotes the label of the $i$-th cup of cocktail. The third line contains $n$ integers separated by a single space such that the $i$-th integer denotes the $i$-th cup of cocktail has deliciousness $a_i$.

Output Specification

The output contains $n$ lines. The $i$-th line contains two integers separated by a single space. The first integer denotes the number of ways to choose two cups of $(i-1)$-similar cocktails. The second integer denotes the maximum possible deliciousness by mixing two cups of cocktails that are $(i-1)$-similar. Notice if there does not exist two cups of cocktail that are $(i-1)$-similar, both integers in that line of the output shall be 0.

Sample Input 1

10
ponoiiipoi
2 1 4 7 4 8 3 6 4 7

Sample Output 1

45 56
10 56
3 32
0 0
0 0
0 0
0 0
0 0
0 0
0 0

Sample Input 2

12
abaabaabaaba
1 -2 3 -4 5 -6 7 -8 9 -10 11 -12

Sample Output 2

66 120
34 120
15 55
12 40
9 27
7 16
5 7
3 -4
2 -4
1 -4
0 0
0 0

Constraints

Test Case	$n$	$a_i$	Additional Constraints
1	$n=100$	$|a_i|\le 10000$
2	$n=200$
3	$n=500$
4	$n=750$
5	$n=1000$	$|a_i|\le 1000000000$
6
7	$n=2000$
8
9	$n=99991$	$|a_i|\le 1000000000$	There will not exist 10-similar cocktails.
10
11	$n=100000$	$|a_i|\le 1000000$	All $a_i$ are equal.
12	$n=200000$
13	$n=300000$
14
15	$n=100000$	$|a_i|\le 1000000000$
16
17	$n=200000$
18
19	$n=300000$
20