Problem Description

The annual "Phantom Pavilion Summer Wine Tasting Festival" has grandly opened. The festival includes two parts: tasting and fun challenges, awarding the "Chief Wine Taster" and "Chief Hunter" titles to the winners, attracting many wine tasters to participate.

At the dinner of the festival, bartender Rainbow prepared \( n \) cocktails. These \( n \) cocktails are arranged in a row, where the \( i \)-th cocktail (\( 1 \leq i \leq n \)) is labeled with a tag \( s_i \), each tag being one of the 26 lowercase English letters. Let \( str(l, r) \) denote the string formed by concatenating the tags of the \( l \)-th to the \( r \)-th cocktails in sequence. If \( str(p, p_0) = str(q, q_0) \), where \( 1 \leq p \leq p_0 \leq n \), \( 1 \leq q \leq q_0 \leq n \), \( p \neq q \), and \( p_0 - p + 1 = q_0 - q + 1 = r \), then the \( p \)-th cocktail and the \( q \)-th cocktail are " \( r \)-similar". Naturally, two " \( r \)-similar" (\( r > 1 \)) cocktails are also " \( 1 \)-similar", " \( 2 \)-similar", ..., " \( (r - 1) \)-similar". Specifically, for any \( 1 \leq p, q \leq n \), \( p \neq q \), the \( p \)-th cocktail and the \( q \)-th cocktail are " \( 0 \)-similar".

In the tasting session, wine taster Freda easily assessed the deliciousness of each cocktail, successfully winning the title of "Chief Wine Taster" with her professional standards and experience. The deliciousness of the \( i \)-th cocktail (\( 1 \leq i \leq n \)) is \( a_i \). Now, Rainbow has announced the challenge question for this session: The cocktails prepared this time have a characteristic, if the \( p \)-th cocktail and the \( q \)-th cocktail are mixed together, they will produce a cocktail with a deliciousness of \( a_p \times a_q \). Now, please count for \( r = 0, 1, 2, \cdots, n-1 \), how many ways there are to choose two " \( r \)-similar" cocktails, and answer the maximum deliciousness that can be obtained by mixing two " \( r \)-similar" cocktails.

Input Format

The first line contains a 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 Format

The output includes \( n \) lines.

The \( i \)-th line outputs 2 integers, separated by a single space. The first integer represents the number of ways to choose two " \( (i - 1) \)-similar" cocktails, and the second integer represents the maximum deliciousness that can be obtained by mixing two " \( (i - 1) \)-similar" cocktails. If there are no " \( (i - 1) \)-similar" cocktails, both numbers are \( 0 \).

Sample Input and Output

Input Sample #1

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

Output Sample #1

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

Input Sample #2

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

Output Sample #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

Notes

Sample Explanation 1

Using the tuple \( (p, q) \) to represent the \( p \)-th cocktail and the \( q \)-th cocktail.

\( 0 \)-similar: All 45 pairs of tuples are \( 0 \)-similar, with the maximum deliciousness being \( 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) \), with the maximum \( 8 \times 7 = 56 \).

\( 2 \)-similar: \( (1,8) (4,9) (5,6) \), with the maximum \( 4 \times 8 = 32 \).

There are no \( 3, 4, 5, \cdots, 9 \)-similar cocktails, so the output is \( 0 \).

Time Limit: 1s, Memory Limit: 512MB

见题面 Input 部分

见题面 Output 部分