La « Dégustation estivale annuelle de 幻影阁 » vient de s’ouvrir en grande pompe. Elle comprend une dégustation et un défi ludique, dont les vainqueurs reçoivent respectivement les titres de « premier dégustateur » et de « premier chasseur ». De nombreux dégustateurs y participent.

Lors du dîner, le barman Rainbow a préparé $n$ cocktails. Ils sont disposés en ligne ; le $i$-ième cocktail ($1\le i\le n$) porte une étiquette $s_i$, qui est l’une des 26 lettres minuscules de l’alphabet anglais. Notons $Str(l,r)$ la chaîne obtenue en concaténant, dans l’ordre, les $r-l+1$ étiquettes des cocktails $l$ à $r$. Si $Str(p,po)=Str(q,qo)$, où $1\le p\le po\le n$, $1\le q\le qo\le n$, $p\ne q$ et $po-p+1=qo-q+1=r$, on dit que les cocktails $p$ et $q$ sont « $r$-similaires ». Bien entendu, deux cocktails « $r$-similaires » ($r>1$) sont aussi « $1$-similaires », « $2$-similaires », …, « $(r-1)$-similaires ». En particulier, pour tous $1\le p,q\le n$ avec $p\ne q$, les cocktails $p$ et $q$ sont « $0$-similaires ».

Lors de la dégustation, Freda a aisément évalué la saveur de chaque cocktail et remporté le titre de « premier dégustateur » grâce à son professionnalisme et à son expérience. La saveur du $i$-ième cocktail ($1\le i\le n$) vaut $a_i$. Rainbow annonce maintenant le défi : les cocktails préparés pour cette édition ont une particularité. En mélangeant les cocktails $p$ et $q$, on obtient un cocktail de saveur $a_pa_q$. Pour chacun des $r=0,1,2,\ldots,n-1$, les dégustateurs doivent déterminer le nombre de façons de choisir 2 cocktails « $r$-similaires », ainsi que la saveur maximale que l’on peut obtenir en mélangeant 2 cocktails « $r$-similaires ».

Entrée

Les données sont lues dans le fichier savour.in.

La première ligne contient un entier strictement positif $n$, le nombre de cocktails.

La deuxième ligne contient une chaîne $S$ de longueur $n$, dont le $i$-ième caractère est l’étiquette du $i$-ième cocktail.

La troisième ligne contient $n$ entiers séparés par un unique espace ; le $i$-ième entier est la saveur $a_i$ du $i$-ième cocktail.

Sortie

Écrivez la sortie dans le fichier savour.out.

Le fichier de sortie comporte $n$ lignes. La $i$-ième ligne contient 2 entiers séparés par un unique espace. Le premier est le nombre de façons de choisir deux cocktails « $(i-1)$-similaires » ; le second est la saveur maximale obtenue en mélangeant deux cocktails « $(i-1)$-similaires ». Si aucune paire de cocktails « $(i-1)$-similaires » n’existe, ces deux nombres valent $0$.

Exemples

Entrée 1

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

Sortie 1

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

Remarque

Le couple $(p,q)$ représente les cocktails $p$ et $q$.

$0$-similaires : les 45 couples sont tous $0$-similaires et la saveur maximale est $8\times7=56$.

$1$-similaires : $(1,8)$, $(2,4)$, $(2,9)$, $(4,9)$, $(5,6)$, $(5,7)$, $(5,10)$, $(6,7)$, $(6,10)$, $(7,10)$ ; la saveur maximale est $8\times7=56$.

$2$-similaires : $(1,8)$, $(4,9)$, $(5,6)$ ; la saveur maximale est $4\times8=32$.

Il n’existe pas de paire de cocktails $3,4,5,\ldots,9$-similaires ; on affiche donc $0$ pour ces valeurs.

Entrée 2

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

Sortie 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

Exemples 3

Voir savour/savour.in et savour/savour.ans dans le répertoire du candidat.

Contraintes

Les bornes et les caractéristiques de tous les tests sont présentées dans le tableau suivant.