“Hội thưởng rượu mùa hè 幻影阁” thường niên đã long trọng khai mạc. Hội gồm hai phần: thưởng thức và thử thách vui, lần lượt trao hai giải “Chuyên gia thưởng rượu hàng đầu” và “Thợ săn hàng đầu” cho người chiến thắng, thu hút đông đảo chuyên gia thưởng rượu tham gia.

Trong bữa tối của hội, người pha chế Rainbow đã pha $n$ ly cocktail. Các ly cocktail này được xếp thành một hàng, trong đó ly thứ $i$ ($1\le i\le n$) được gắn nhãn $s_i$, mỗi nhãn là một trong $26$ chữ cái tiếng Anh viết thường. Gọi $Str(l,r)$ là chuỗi tạo thành bằng cách nối lần lượt $r-l+1$ nhãn từ ly thứ $l$ đến ly thứ $r$. Nếu $Str(p,po)=Str(q,qo)$, trong đó $1\le p\le po\le n$, $1\le q\le qo\le n$, $p\ne q$, $po-p+1=qo-q+1=r$, thì gọi ly thứ $p$ và ly thứ $q$ là “tương tự mức $r$”. Dĩ nhiên, hai ly “tương tự mức $r$” ($r>1$) đồng thời cũng “tương tự mức $1$”, “tương tự mức $2$”, …, “tương tự mức $(r-1)$”. Đặc biệt, với mọi $1\le p,q\le n$, $p\ne q$, ly thứ $p$ và ly thứ $q$ đều “tương tự mức $0$”.

Trong phần thưởng thức, chuyên gia Freda dễ dàng đánh giá độ ngon của từng ly rượu, dựa vào trình độ chuyên môn và kinh nghiệm của mình để giành danh hiệu “Chuyên gia thưởng rượu hàng đầu”; độ ngon của ly thứ $i$ ($1\le i\le n$) là $a_i$. Bây giờ Rainbow công bố câu hỏi của phần thử thách: những ly cocktail được pha tại hội lần này có một đặc điểm, nếu trộn ly thứ $p$ với ly thứ $q$ thì thu được một ly có độ ngon $a_pa_q$. Với từng $r=0,1,2,\ldots,n-1$, hãy đếm có bao nhiêu cách chọn $2$ ly “tương tự mức $r$”, đồng thời trả lời độ ngon lớn nhất có thể thu được khi trộn $2$ ly “tương tự mức $r$”.

Dữ liệu vào

Đọc dữ liệu từ tệp savour.in.

Dòng đầu tiên của tệp chứa một số nguyên dương $n$, biểu thị số ly cocktail.

Dòng thứ $2$ chứa một chuỗi $S$ có độ dài $n$, trong đó ký tự thứ $i$ biểu thị nhãn của ly thứ $i$.

Dòng thứ $3$ chứa $n$ số nguyên, các số nguyên liên tiếp được ngăn cách bởi một dấu cách; số nguyên thứ $i$ biểu thị độ ngon $a_i$ của ly thứ $i$.

Dữ liệu ra

Ghi kết quả vào tệp savour.out.

Tệp kết quả gồm $n$ dòng. Dòng thứ $i$ in $2$ số nguyên ngăn cách bởi một dấu cách. Số thứ nhất biểu thị số cách chọn hai ly “tương tự mức $(i-1)$”; số thứ hai biểu thị độ ngon lớn nhất có thể thu được khi trộn hai ly “tương tự mức $(i-1)$”. Nếu không tồn tại hai ly “tương tự mức $(i-1)$” thì cả hai số đều bằng $0$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

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

Ghi chú

Dùng cặp $(p,q)$ để biểu thị ly thứ $p$ và ly thứ $q$.

Tương tự mức $0$: tất cả $45$ cặp đều tương tự mức $0$, độ ngon lớn nhất là $8\times 7=56$.

Tương tự mức $1$: $(1,8)$ $(2,4)$ $(2,9)$ $(4,9)$ $(5,6)$ $(5,7)$ $(5,10)$ $(6,7)$ $(6,10)$ $(7,10)$, giá trị lớn nhất là $8\times 7=56$.

Tương tự mức $2$: $(1,8)$ $(4,9)$ $(5,6)$, giá trị lớn nhất là $4\times 8=32$.

Không có hai ly nào tương tự mức $3,4,5,\ldots,9$, nên đều in $0$.

Dữ liệu vào 2

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

Dữ liệu ra 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

Ví dụ 3

Xem các tệp savour/savour.in và savour/savour.ans trong thư mục của thí sinh.

Giới hạn

Phạm vi và đặc điểm của mọi dữ liệu kiểm thử được cho trong bảng dưới đây.