题目描述

给定一个长度为 $n$ 的字符串 $s$。

定义长度为 $L$ 的子串 $s[i, i+L-1]$ 的起点为 $i(1\leq i \leq n)$。

对于长度为 $L$ 的所有子串，按照字典序从小到大排序(字典序相同时按照起点从小到大)后，子串的起点形成的序列 $G=[ g_1, g_2, ... , g_{n-L+1}](1\leq g_i \leq n-L+1)$

定义 $$f(L)=\sum_{i=1}^{n-L+1} g_i*i$$

对于所有$1 \leq L \leq n$，输出 $f(L)$

输入格式

一个长度为 $n$ 的字符串 $s$。

输出格式

共一行，包含 $n$ 个整数，第 $i$ 个整数为 $f(i)$

样例

输入样例

cba

输出样例

10 4 1

样例解释

L=1, G=[3,2,1], F(1)=10

L=2, G=[2,1], F(2)=4

L=3, G=[1], F(3)=1

提示

对于 $\red{50\% }$的数据 $\red{n\leq 500}$

对于 $\red{100\% }$的数据 $\red{n\leq 5000}$