给你一个字符串 $$$s$$$,由小写拉丁字母组成。
系统会向您提出 $$$q$$$ 查询:给定另一个由小写拉丁字母组成的字符串 $$$t$$$,执行以下步骤:
1. 连接$$$s$$$ 和$$$t$$$;
2.计算结果字符串$$$s+t$$$的前缀函数;
3. 在 $$$|s|+1、|s|+2、\dots、|s|+|t|$$$ 位置打印前缀函数的值($$$|s|$$$ 和 $$$|t|$$$ 分别表示字符串 $$$s$$$ 和 $$$t$$$ 的长度);
4. 将字符串恢复为 $$$s$$$。
字符串 $$$a$$$ 的前缀函数是序列 $$$p_1, p_2, \dots, p_{|a|}$$$,其中 $$$p_i$$$ 是 $$$k$$$ 的最大值,使得 $$$k < i$$$ 且 $$$a[1..k]=a[i-k+1..i]$$$ ($$$a[l..r]$$$ 表示字符串 $$$a$$$ 中从位置 $$$l$$$ 到位置 $$$r$$$ 的连续子串(含)。换句话说,它是字符串 $$$a[1..i]$$$ 的最长的正确前缀,等于其相同长度的后缀。
输入
第一行包含一个非空字符串 $$$s$$$ ($$$1 \le |s| \le 10^6$$$),由小写拉丁字母组成。
第二行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。
接下来的 $$$q$$$ 行都包含一个查询:一个非空字符串 $$$t$$$ ($$$1 \le |t| \le 10$$$),由小写拉丁字母组成。
输出
对于每个查询,在位置 $$$|s|+1、|s|+2、\dots、|s|+|t|$$$ 上打印字符串 $$$s+t$$$ 的前缀函数的值。
示例
输入 #1
aba 6 caba aba bababa aaaa b forces
输出 #1
0 1 2 3 1 2 3 2 3 4 5 6 7 1 1 1 1 2 0 0 0 0 0 0
输入 #2
aacba 4 aaca cbbb aab ccaca
输出 #2
2 2 3 1 0 0 0 0 2 2 0 0 0 1 0 1