前缀函数查询

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个由小写拉丁字母组成的字符串 $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+t$ 的前缀函数在位置 $|s|+1, |s|+2, \dots, |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

数据范围