题目描述

给定一个长度为 $n$ 的字符串。对于每个长度 $1,2,\ldots,n$，请输出不同子串的数量。

输入格式

输入一行，包含一个长度为 $n$、仅由小写英文字母组成的字符串。

输出格式

输出 $n$ 个整数，第 $i$ 个整数表示长度为 $i$ 的不同子串数量。

数据范围

• $1 \le n \le 10^5$

样例

样例输入

abab

样例输出

2 2 2 1