winetasting

Wine Tasting Conference

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 "1-alike", "2-alike", and "\((r - 1)\)-alike". In particular, for any \(1 \leq p\), \(q \leq n\), \(p \neq q\), the \(p^{th}\) glass is "0-alike" 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 "r-alike" cocktails, and also find the maximum tastiness that can be obtained by blending two "r-alike" cocktails.

Limits

\(1 \leq n \leq 3 \times 10^5\), \(1 \leq |a_i| \leq 10^9\).

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 10-alike cocktails exist.
4	20	All values of \(a_i\) are equal.
5	30	No additional constraints

Input format

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 format

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.

Samples

Sample Input 1	Sample Output 1
10 ponoiiipoi 2 1 4 7 4 8 3 6 4 7	45 56 10 56 3 32 0 0 0 0 0 0 0 0 0 0 0 0 0 0

• 0-alike: All 45 pairs of cocktails are 0-alike. The tastiest mix has tastiness \(8 \times 7 = 56\).
• 1-alike: The 1-alike pairs of cocktails are \((1, 8), (2, 4), (2, 9), (4, 9), (5, 6), (5, 7), (5, 10), (6, 7), (6, 10)\), and \((7, 10)\). The tastiest mix remains \(8 \times 7 = 56\).
• 2-alike: The 2-alike pairs of cocktails are \((1, 8), (4, 9)\), and \((5, 6)\). The tastiest of them has tastiness \(4 \times 8 = 32\).
• No pairs of cocktails are 3-alike, 4-alike, \(\ldots\), or 9-alike.

Sample Input 2	Sample Output 2
12 abaabaabaaba 1 -2 3 -4 5 -6 7 -8 9 -10 11 -12	66 120 34 120 15 55 12 40 9 27 7 16 5 7 3 -4 2 -4 1 -4 0 0 0 0