칵테일 파티

길이가 $n$인 문자열이 주어진다. 이 문자열은 $n$개의 칵테일 컵에 붙은 라벨이며, 각 $i$번째 컵의 라벨은 $s_i$이다. 모든 라벨은 소문자 영어 알파벳 26개 중 하나이다. $\mathrm{Str}(l,r) = s_l s_{l+1} \cdots s_r$은 $l$번째 컵부터 $r$번째 컵까지의 라벨로 이루어진 문자열이다. $1 \le p \le p_0 \le n$, $1 \le q \le q_0 \le n$, $p \ne q$, $p_0-p+1 = q_0-q+1 = r$일 때 $\mathrm{Str}(p,p_0) = \mathrm{Str}(q,q_0)$이면, $p$번째 컵과 $q$번째 컵을 $r$-similar하다고 한다. 어떤 $r > 1$에 대해 두 컵이 $r$-similar하면, 이 두 컵은 $1$-similar, $2$-similar, ..., $(r-1)$-similar하기도 하다. $1 \le p \le q \le n$이고 $p \ne q$인 모든 두 컵은 $0$-similar하다.

Freda는 각 컵에 맛있는 정도 $a_i$를 매겼다. $p$번째 컵과 $q$번째 컵을 섞으면 맛있는 정도가 $a_p a_q$인 칵테일이 만들어진다. $r = 0, \dots, n-1$마다 $r$-similar한 두 컵을 고르는 방법의 수와, $r$-similar한 두 컵을 섞어 얻을 수 있는 맛있는 정도의 최댓값을 구하라.

첫째 줄에 컵의 개수 $n$이 주어진다. 둘째 줄에는 길이가 $n$인 문자열 $S$가 주어지며, $i$번째 문자가 $i$번째 컵의 라벨이다. 셋째 줄에는 $n$개의 정수가 공백으로 구분되어 주어지며, $i$번째 정수가 $a_i$이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 두 정수를 공백으로 구분하여 출력한다. 첫 번째 정수는 $(i-1)$-similar한 두 컵을 고르는 방법의 수이고, 두 번째 정수는 $(i-1)$-similar한 두 컵을 섞어 얻을 수 있는 맛있는 정도의 최댓값이다. $(i-1)$-similar한 두 컵이 존재하지 않으면 그 줄에 0 0을 출력한다.

$10 \le n \le 300\,000$

$|a_i| \le 1\,000\,000\,000$