The annual "Phantom Pavilion Summer Wine Tasting Festival" has grandly opened. The festival consists of two parts: tasting and fun challenges, with the "Chief Sommelier" and "Chief Hunter" awards presented to the winners, attracting many sommeliers to participate.

At the festival dinner, the bartender Rainbow prepared $n$ cocktails. These $n$ cocktails are arranged in a row, where the $i$-th cocktail ($1 \le i \le n$) is labeled with a tag $s_i$, and each tag is one of the 26 lowercase English letters. Let $Str(l, r)$ denote the string formed by concatenating the tags of the $i$-th cocktail to the $r$-th cocktail in order. If $Str(p, p+k-1) = Str(q, q+k-1)$, where $1 \le p \le p+k-1 \le n$, $1 \le q \le q+k-1 \le n$, $p \neq q$, and the length of the strings is $k$, then the $p$-th cocktail and the $q$-th cocktail are said to be "$k$-similar". Of course, two "$r$-similar" ($r > 1$) cocktails are also "1-similar", "2-similar", ..., "$(r-1)$-similar". Specifically, for any $1 \le p, q \le n, p \neq q$, the $p$-th cocktail and the $q$-th cocktail are always "0-similar".

In the tasting session, the sommelier Freda easily evaluated the deliciousness of each cocktail and, relying on her professional standards and experience, successfully won the title of "Chief Sommelier". The deliciousness of the $i$-th cocktail ($1 \le i \le n$) is $a_i$. Now Rainbow has announced the problem for the challenge session: the cocktails prepared for this festival have a characteristic where if the $p$-th cocktail and the $q$-th cocktail are mixed together, the resulting cocktail has a deliciousness of $a_p \times a_q$. Now, for each $k = 0, 1, 2, \dots, n-1$, please calculate how many ways there are to choose two "$k$-similar" cocktails, and answer the maximum deliciousness that can be obtained by mixing two "$k$-similar" cocktails.

Input

The input is read from the file savour.in. The first line of the input file contains a single positive integer $n$, representing the number of cocktails. The second line contains a string $S$ of length $n$, where the $i$-th character represents the tag of the $i$-th cocktail. The third line contains $n$ integers, separated by single spaces, where the $i$-th integer represents the deliciousness $a_i$ of the $i$-th cocktail.

Output

Output to the file savour.out. The output file includes $n$ lines. The $(k+1)$-th line outputs 2 integers, separated by a single space. The first integer represents the number of ways to choose two "$k$-similar" cocktails, and the second integer represents the maximum deliciousness that can be obtained by mixing two "$k$-similar" cocktails. If there are no two "$k$-similar" cocktails, both numbers are 0.

Examples

Input 1

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

Output 1

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

Note 1

Using the tuple $(p, q)$ to represent the $p$-th cocktail and the $q$-th cocktail: 0-similar: All 45 pairs are 0-similar, the maximum deliciousness is $8 \times 7 = 56$. 1-similar: $(1,8), (2,4), (2,9), (4,9), (5,6), (5,7), (5,10), (6,7), (6,10), (7,10)$, the maximum is $8 \times 7 = 56$. 2-similar: $(1,8), (4,9), (5,6)$, the maximum is $4 \times 8 = 32$. There are no 3, 4, 5, ..., 9-similar pairs, so output 0 for these.

Input 2

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

Output 2

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

Input 3

0 0

(See savour/savour.in and savour/savour.ans in the contestant directory.)

Constraints

The ranges and characteristics of all test data are shown in the table below: