假设有两个字符串 s 和 t,并且它们的长度相等。您可以多次执行以下操作:选择两个不同的字符 c1 和 c2,并将两个字符串中每次出现的 c1 替换为 c2。我们将字符串 s 和 t 之间的距离表示为使这些字符串相等所需的最少操作数。例如,如果 s 是 abcd,t 是 ddcb,它们之间的距离是 2——我们可以将每次出现的 a 替换为 b,因此 s 变为 bbcd,然后我们可以将每次出现的 b 替换为 d,因此两个字符串都变为 ddcd。
给定两个字符串 S 和 T。对于 S 的每个由 |T| 组成的子字符串您必须确定该子字符串与 T 之间的距离。
输入
第一行包含字符串 S,第二行包含字符串 T (1 ≤ |T| ≤ |S| ≤ 125000)。两个字符串均由从 a 到 f 的小写拉丁字母组成。
输出
打印 |S| -|T| + 1 个整数。这些整数中的第 i 个必须等于 S 中从第 i 个索引开始、长度为 |T| 的子串之间的距离。和字符串 T。
示例
输入 #1
abcdefa ddcb
输出 #1
2 3 3 3