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\le i\le 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\le p_0\le p\le n$, $1\le q_0\le q\le n$, $p\ne 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\le p$, $q\le n$, $p\ne 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\le i\le 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\ast a_q$. He asks the sommeliers: For each $r=0,1,2,\dots ,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\le n\le 3\times {10}^5$, $1\le |a_i|\le {10}^9$.

Subtask #	Score	Constraints
1	15	$n\le 500$ $|a_i|\le 10000$
2	25	$n\le 2000$
3	10	$n\le 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, $\dots$, 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