Торжественно открылся ежегодный «Летний дегустационный фестиваль 幻影阁». Он включает дегустацию и занимательное испытание, победителям которых вручаются звания «Главный дегустатор» и «Главный охотник». Фестиваль привлёк множество дегустаторов.

На праздничном ужине бармен Rainbow приготовил $n$ коктейлей и выстроил их в ряд. Коктейль $i$ ($1\le i\le n$) помечен этикеткой $s_i$ — одной из 26 строчных английских букв. Обозначим через $Str(l,r)$ строку, полученную последовательным соединением $r-l+1$ этикеток коктейлей с $l$ по $r$. Если $Str(p,po)=Str(q,qo)$, где $1\le p\le po\le n$, $1\le q\le qo\le n$, $p\ne q$, $po-p+1=qo-q+1=r$, то коктейли $p$ и $q$ называются «$r$-похожими». Разумеется, два «$r$-похожих» коктейля при $r>1$ также являются «$1$-похожими», «$2$-похожими», …, «$(r-1)$-похожими». В частности, для любых $1\le p,q\le n$, $p\ne q$ коктейли $p$ и $q$ являются «$0$-похожими».

Во время дегустации Freda с лёгкостью оценила вкус каждого коктейля и благодаря профессионализму и опыту завоевала звание «Главный дегустатор». Вкус коктейля $i$ ($1\le i\le n$) оценён числом $a_i$. Теперь Rainbow объявил задание испытания: у приготовленных на этом фестивале коктейлей есть особенность — если смешать коктейли $p$ и $q$, получится коктейль с оценкой вкуса $a_pa_q$. Для каждого $r=0,1,2,\ldots,n-1$ подсчитайте количество способов выбрать 2 «$r$-похожих» коктейля и определите максимально возможную оценку вкуса, которую можно получить их смешиванием.

Входные данные

Данные считываются из файла savour.in.

Первая строка входного файла содержит положительное целое число $n$ — количество коктейлей.

Вторая строка содержит строку $S$ длины $n$, символ $i$ которой является этикеткой коктейля $i$.

Третья строка содержит $n$ целых чисел, разделённых одиночными пробелами. Число $i$ задаёт оценку вкуса $a_i$ коктейля $i$.

Выходные данные

Выведите результат в файл savour.out.

Выходной файл должен содержать $n$ строк. В строке $i$ выведите два целых числа, разделённых одним пробелом. Первое — количество способов выбрать два «$(i-1)$-похожих» коктейля, второе — максимально возможная оценка вкуса при смешивании двух «$(i-1)$-похожих» коктейлей. Если таких двух коктейлей нет, оба числа должны быть равны $0$.

Примеры

Входные данные 1

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

Выходные данные 1

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

Примечание

Парой $(p,q)$ обозначим коктейли $p$ и $q$.

$0$-похожие: все 45 пар являются $0$-похожими; максимальная оценка вкуса равна $8\times7=56$.

$1$-похожие: $(1,8)$, $(2,4)$, $(2,9)$, $(4,9)$, $(5,6)$, $(5,7)$, $(5,10)$, $(6,7)$, $(6,10)$, $(7,10)$; максимальная оценка равна $8\times7=56$.

$2$-похожие: $(1,8)$, $(4,9)$, $(5,6)$; максимальная оценка равна $4\times8=32$.

Двух коктейлей, похожих при $r=3,4,5,\ldots,9$, нет, поэтому для них выводятся нули.

Входные данные 2

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

Выходные данные 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

Пример 3

См. файлы savour/savour.in и savour/savour.ans в каталоге участника.

Ограничения

Диапазоны и особенности всех тестов приведены в следующей таблице.