题目描述

DNA 串为只由 $\tt ATGC$ 四种字母组成的字符串，称一个 DNA 串 $S$ 为可转录的，当且仅当其存在一个子串是给定的 DNA 串 $T$。

设 $n$ 为 $S$ 的长度，对于 $i=1,2,\ldots,n$，你需要求出长度为 $i$ 的可转录子串有多少个。

对于一个字符串，定义其子串为删去原串首尾任意数量（可以为 $0$）的字符得到的新字符串，两个子串相同当且仅当首尾删去的字符个数分别相同。

输入格式

第一行输入一个字符串 $S$。

第二行输入一个字符串 $T$。

输出格式

输出一行 $n$ 个正整数，第 $i$ 个正整数表示长度为 $i$ 的可转录子串的个数。

ATGACT
GA

0 1 2 3 2 1

ATATAC
ATA

0 0 2 3 2 1 

ATGAATGAAGAT
AA

0 2 4 6 8 7 6 5 4 3 2 1 

提示

对于样例 #1，可转录的子串有 $\tt GA$，$\tt TGA$，$\tt GAC$，$\tt ATGA$，$\tt TGAC$，$\tt GACT$，$\tt ATGAC$，$\tt TGACT$，$\tt ATGACT$。

对于样例 #2，可转录的子串有 $\tt ATA$，$\tt ATA$，$\tt ATAT$，$\tt TATA$，$\tt ATAC$，$\tt ATATA$，$\tt TATAC$，$\tt ATATAC$。

记 $n$ 为 $S$ 的长度，$m$ 为 $T$ 的长度。

对于前 $10\%$ 的数据，保证 $m=1$。

对于前 $50\%$ 的数据，保证 $1\leq n\leq 100$。

对于 $100\%$ 的数据，保证 $1\leq m\leq n\leq 1000$，$S,T$ 中仅包含 $\tt ATGC$ 四种字母。