Description

给出模板串A和子串B，长度分别为lenA和lenB

要求在线性时间内，对于每个A[i]（1<=i<=lenA)，求出A[i..lenA]与B的最长公共前缀长度

Format

Input

输入A，B两个串，（lenB<=lenA<=1000000)

Output

输出lenA个数，表示A[i...lenA]与B的最长公共前缀长度，每个数之前有空格

Samples

aabbabaaab
aabb

4 1 0 0 1 0 2 3 1 0