The annual "Mirage Pavillion Summer Wine Tasting Conference" has just witnessed its grand opening. The event consisted of a Tasting Challenge and a Fun Challenge, with two prizes awarded to the winners, "Top Sommelier" and "Top Hunter", attracting many tasters to participate.
At the conference dinner, the bartender Rainbow made \(n\) cocktails. The cocktails were arranged in a row, with the \(i^{th}\) glass \((1 \leq i \leq n)\) labelled one of the 26 lowercase letters of the alphabet \(s_i\). Let \(Str(l, r)\) denote the string consisting of the sequentially concatenated \(r  l + 1\) labels of the the \(l^{th}\) glass to the \(r^{th}\) glass. If \(Str(p, p_0) = Str(q, q_0)\), where \(1 \leq p_0 \leq p \leq n\), \(1 \leq q_0 \leq q \leq n\), \(p \neq q\), and \(p_0  p + 1 = q_0  q + 1 = r\), then the \(p^{th}\) glass is said to be "\(r\)alike" to the \(q^{th}\) glass. Of course, two glasses of wine that are "\(r\)alike" \((r > 1)\) are also "1alike", "2alike", and "\((r  1)\)alike". In particular, for any \(1 \leq p\), \(q \leq n\), \(p \neq q\), the \(p^{th}\) glass is "0alike" to the \(q^{th}\) glass.
During the tasting session, Sommelier Freda assessed the tastiness of each drink, and with her professionalism and experience easily won the title of "Top Sommelier". The \(i^{th}\) drink \((1 \leq i \leq n)\) was hence rated \(a_i\). Rainbow then announced the question for the Fun Challenge: If the \(p^{th}\) cocktail were to be mixed with the \(q^{th}\) cocktail, you would get a drink with tastiness \(a_p * a_q\). He asks the sommeliers: For each \(r = 0, 1, 2, \ldots, n  1\), count the number of ways to select two "ralike" cocktails, and also find the maximum tastiness that can be obtained by blending two "ralike" cocktails.
Subtask #  Score  Constraints 

1  15  \(n \leq 500\) \(a_i \leq 10000\) 
2  25  \(n \leq 2000\) 
3  10  \(n \leq 99991\) No pairs of 10alike cocktails exist. 
4  20  All values of \(a_i\) are equal. 
5  30  No additional constraints 
The first line of input consists of a single integer \(n\), the number of glasses of cocktails.
The second line of input consists of a length \(n\) string of lowercase letters \(S\), the \(i^{th}\) character of which represents glass \(i\)'s label.
The third line of input contains \(n\), the \(i^{th}\) of which represents the tastiness \(a_i\) of cocktail \(i\).
Output \(n\) lines each containing two integers. On the \(i^{th}\) line, the first integer shall be the number of ways to choose two \((i  1)\)alike cocktail glasses, and the second integer shall be the greatest tastiness achievable by mixing two \((i  1)\)alike cocktails. If no pairs of \((i  1)\)alike cocktails exist, output 0 for both integers.
Sample Input 1  Sample Output 1 
10

45 56

Sample Input 2  Sample Output 2 
12

66 120

Subtask  Score 

1  15 
2  25 
3  10 
4  20 
5  30 