一年一度的「幻影閣夏日品酒大會」隆重開幕了。大會包含品嚐和趣味挑戰兩個環節，分別向優勝者頒發「首席品酒家」和「首席獵手」兩個獎項，吸引了眾多品酒師參加。

在大會的晚餐上，調酒師 Rainbow 調製了 $n$ 杯雞尾酒。這 $n$ 杯雞尾酒排成一行，其中第 $i$ 杯酒（$1\le i\le n$）被貼上了一個標籤 $s_i$，每個標籤都是 26 個小寫英文字母之一。設 $Str(l,r)$ 表示第 $l$ 杯酒到第 $r$ 杯酒的 $r-l+1$ 個標籤依序連接構成的字串。若 $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,\cdots,n-1$，統計出有多少種方法可以選出 2 杯「$r$ 相似」的酒，並回答選擇 2 杯「$r$ 相似」的酒調兌可以得到的美味度的最大值。

輸入格式

從檔案 savour.in 中讀入資料。

輸入檔案的第 1 行包含 1 個正整數 $n$，表示雞尾酒的杯數。

第 2 行包含一個長度為 $n$ 的字串 $S$，其中第 $i$ 個字元表示第 $i$ 杯酒的標籤。

第 3 行包含 $n$ 個整數，相鄰整數之間用單個空格隔開，其中第 $i$ 個整數表示第 $i$ 杯酒的美味度 $a_i$。

輸出格式

輸出到檔案 savour.out 中。

輸出檔案包括 $n$ 行。第 $i$ 行輸出 2 個整數，中間用單個空格隔開。第 1 個整數表示選出兩杯「$(i-1)$ 相似」的酒的方案數，第 2 個整數表示選出兩杯「$(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\times 7=56$。

$1$ 相似：$(1,8)\ (2,4)\ (2,9)\ (4,9)\ (5,6)\ (5,7)\ (5,10)\ (6,7)\ (6,10)\ (7,10)$，最大的 $8\times 7=56$。

$2$ 相似：$(1,8)\ (4,9)\ (5,6)$，最大的 $4\times 8=32$。

沒有 $3,4,5,\cdots,9$ 相似的兩杯酒，故均輸出 $0$。

輸入格式 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。

資料範圍

所有測試資料的範圍和特點如下表所示。