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

喺大會嘅晚餐上，調酒師 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,\ldots,n-1$，統計有幾多種方法可以揀出 2 杯「$r$ 相似」嘅酒，並且回答揀 2 杯「$r$ 相似」嘅酒混合，可以得到嘅美味度最大值。

輸入格式

由檔案 savour.in 讀入資料。

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

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

第三行包含 $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,\ldots,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。

資料規模同約定

所有測試資料嘅範圍同特點如下表：