两个字符串之间的 Levenshtein 距离是将一个字符串转换为另一个字符串所需的最少单字符操作次数。这些操作包括：

• 在字符串的任意位置添加一个字母。
• 从字符串的任意位置删除一个字母。
• 将字符串中的任意字母更改为其他任何字母。

给定一个整数 $k$ 和两个字符串 $S$ 和 $T$。你的任务是对于每个可能的非负整数 $i$ ($0 \le i \le k$)，求出 $T$ 中有多少个非空子串与 $S$ 的 Levenshtein 距离恰好为 $i$。如果两个子串在 $T$ 中出现的位置不同，则它们被视为不同的子串。

输入格式

第一行包含一个整数 $k$ ($0 \le k \le 30$)，表示参数 $k$。 第二行包含一个字符串 $S$ ($1 \le |S| \le 10^5$)，表示模式串。 第三行包含一个字符串 $T$ ($1 \le |T| \le 10^5$)，表示文本串。

保证输入字符串仅由小写英文字母（'a' 到 'z'）、大写英文字母（'A' 到 'Z'）和数字（'0' 到 '9'）组成。

输出格式

输出 $k+1$ 行，第 $i$ 行（$1 \le i \le k+1$）包含一个整数，表示 $T$ 中与 $S$ 的 Levenshtein 距离恰好为 $i-1$ 的子串数量。

样例

样例输入 1

4
aaa
aabbaab

样例输出 1

0
5
15
7
1