You are given a string of length representing the labels of cups of cocktail. The -th cup of cocktail has label , and the labels are among the 26 lowercase English letters. Let be the string formed by the labels of the cocktails from the -th cup to the -th cup. If where , , , , we say the -th cup of cocktail and -th cup of cocktail are -similar. Of course, for two cups of cocktail that are -similar () they are also 1-similar, 2-similar, ..., and -similar. In particular, for any , the -th cup of cocktail and -th cup of cocktail are -similar.
Freda assigns the "deliciousness" for each cup of cocktail, and the -th cup has deliciousness . If we mix -th cup of cocktail and -th cup of cocktail, we may obtain cocktail with deliciousness . The problem asks for each , how many ways we may select two cups of cocktail that are -similar, and compute the maximum possible deliciousness by mixing two cups of cocktail that are -similar.
Input Specification
The first line of the input contains an integer denoting the number of cups of cocktail. The second line contains a string with length such that the -th character denotes the label of the -th cup of cocktail. The third line contains integers separated by a single space such that the -th integer denotes the -th cup of cocktail has deliciousness .
Output Specification
The output contains lines. The -th line contains two integers separated by a single space. The first integer denotes the number of ways to choose two cups of -similar cocktails. The second integer denotes the maximum possible deliciousness by mixing two cups of cocktails that are -similar. Notice if there does not exist two cups of cocktail that are -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 | Additional Constraints | ||
---|---|---|---|
1 | |||
2 | |||
3 | |||
4 | |||
5 | |||
6 | |||
7 | |||
8 | |||
9 | There will not exist 10-similar cocktails. | ||
10 | |||
11 | All are equal. | ||
12 | |||
13 | |||
14 | |||
15 | |||
16 | |||
17 | |||
18 | |||
19 | |||
20 |
Comments