对于一个字符串 $u = u_1 \dots u_n$，Bobo 将前缀 $u_1 \dots u_i$ 记为 $\text{pre}(u, i)$。类似地，他将后缀 $u_{n-i+1} \dots u_n$ 记为 $\text{suf}(u, i)$。特别地，$\text{pre}(u, 0)$ 和 $\text{suf}(u, 0)$ 为空字符串。

对于两个字符串 $u = u_1 \dots u_n$ 和 $v = v_1 \dots v_m$，Bobo 将拼接后的字符串 $u_1 \dots u_n v_1 \dots v_m$ 记为 $u + v$。 此外， $$\text{presuf}(u, v) = \max\{i \mid i < n \text{ 且 } i \le m \text{ 且 } \text{pre}(u, i) = \text{suf}(v, i)\}$$。

给定两个字符串 $s = s_1 \dots s_n$ 和 $t = t_1 \dots t_m$，令 $f(i) = \text{presuf}(s, \text{pre}(s, i) + t)$。求 $f(0), \dots, f(n - 1)$ 的值。

输入格式

输入包含多组测试数据，以文件结束符（EOF）终止。对于每组测试数据： 第一行包含一个字符串 $s_1 \dots s_n$。 第二行包含一个字符串 $t_1 \dots t_m$。

• $1 \le n, m \le 10^6$
• 对于每个 $1 \le i \le n$，$s_i \in \{a, \dots, z\}$
• 对于每个 $1 \le i \le m$，$t_i \in \{a, \dots, z\}$
• 在每组输入中，$\max(n, m)$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出 $n$ 个整数，表示 $f(0), \dots, f(n - 1)$。

样例

输入格式 1

aaa
a
ababa
a
ab
cd

输出格式 1

1 2 2
1 1 3 1 3
0 0

说明

对于第二组样例，$f(4) = \text{presuf}(s, \text{pre}(s, 4) + t) = \text{presuf}(\text{ababa}, \text{abab} + a) = \text{presuf}(\text{ababa}, \text{ababa})$。

因此，$f(4) = 3$。