题目描述

小蓝非常喜欢幸运字符串，幸运字符串指的是字符串中的一个前缀，现在给定你一个长度为$n$的字符串$S$，要求你数出这个字符串中对于每个幸运字符串总共出现了多少次？

输入格式

第一行给定一个正整数$n$。

第二行输入一个由小写字母组成的字符串表示字符串$S$。

输出格式

每次输出一个正整数，表示答案。

样例输入输出

6
abcabc

9

说明

对于前缀$a, ab, abc, abca, abcab, abcabc$字符串中分别出现2,2,2,1,1,1,所以答案为为$3 \times 2 + 3 \times 1= 9$。

数据规模

对于100%的评测数据：

$1\leqslant n \leqslant 2 \times 10^5$。