Migrated from Lutece 2648 ドンドンド一ナツ！どんと行こう！

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

甜甜圈店 Mr.Donut 里有 $26$ 种甜甜圈，让我们用 $26$ 个小写字母 $\texttt a$ 到 $\texttt z$ 表示。

今天的 Mr.Donut 正在搞促销活动，店里所有的 $n$ 个甜甜圈都排成了一行，第 $i$ 个甜甜圈的种类是 $s_i$，每一个甜甜圈上都有一张标签 $b_i$，标明了活动价格。

活动规定：顾客可以任意选择两个甜甜圈，假设是第 $p$ 个和第 $q$ 个。$\text{str}(l,r)$ 表示从 $l$ 到 $r$ 总共 $r-l+1$ 个甜甜圈的序列，若 $\text{str}(p,p_0)=\text{str}(q,q_0)$，其中 $1\le p\le p_0\le n, 1\le q\le q_0\le n, p\neq q, p_0−p+1=q_0−q+1=x$，那么顾客的中奖等级为 $x$，即中了 $x$ 等奖。只需要支付两个甜甜圈的活动价格的乘积 $b_pb_q$，就可以带走两个序列中所有的 $2x$ 个甜甜圈（重叠部分会给两个）。很明显，中 $x$ 等奖的同时也可以说是中了 $0$ 到 $x-1$ 等奖。特别的，随便选两个都能中第 $0$ 等奖（付钱也拿不走任何一个甜甜圈！）。

shinobu 和垃圾君又一次来到 Mr.Donut 店门口，突然发现在搞活动。shinobu 对这个活动很不满，所以她把某些甜甜圈标签上的价格改成了负数，这样她就有机会在没有钱的情况下白嫖甜甜圈。

现在 shinobu 想知道中 $0$ 到 $n-1$ 等奖分别共有多少种不同的选择法，以及所有这些不同选法中的最坏情况（即需要支付的最大价钱）。shinobu 问垃圾君，垃圾君可算不来，于是他向你求助：「那你能帮帮我吗？」。

Input

第一行包含一个正整数 $n$，表示甜甜圈的个数。

第二行包含一个长度为 $n$ 的字符串 $s$，其中 $s_i$ 表示第 $i$ 个甜甜圈的种类。

第三行包含 $n$ 个整数，其中第 $i$ 个整数 $b_i$ 表示第 $i$ 个甜甜圈被 shinobu 修改过后的标签价格。

Output

输出 $n$ 行。

第 $i$ 行输出两个整数，分别代表中 $i-1$ 等奖的不同的选择法，以及所有这些不同选法中需要支付的最大价钱。若不存在任何一种选择法，这两个数输出均为 $0$。

Samples

13
oshinoshinobu
3 5 2 4 1 4 0 9 -1 1 10 5 1

78 90
7 40
5 18
4 18
3 18
2 12
1 12
0 0
0 0
0 0
0 0
0 0
0 0

Constraints

$1\le n\le 3\times 10^5$ $0\le |b_i|\le 10^9$

Resources

2021 UESTC ICPC Training for String and Search Algorithm