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 10\,000~
2	~n = 200~
3	~n = 500~
4	~n = 750~
5	~n = 1000~	~|a_i| \le 1\,000\,000\,000~
6
7	~n = 2000~
8
9	~n = 99\,991~	~|a_i| \le 1\,000\,000\,000~	There will not exist 10-similar cocktails.
10
11	~n = 100\,000~	~|a_i| \le 1\,000\,000~	All ~a_i~ are equal.
12	~n = 200\,000~
13	~n = 300\,000~
14
15	~n = 100\,000~	~|a_i| \le 1\,000\,000\,000~
16
17	~n = 200\,000~
18
19	~n = 300\,000~
20