CF1721E.Prefix Function Queries

You are given a string $s$, consisting of lowercase Latin letters.

You are asked $q$ queries about it: given another string $t$, consisting of lowercase Latin letters, perform the following steps:

1. concatenate $s$ and $t$;
2. calculate the prefix function of the resulting string $s+t$;
3. print the values of the prefix function on positions $|s|+1, |s|+2, \dots, |s|+|t|$ ($|s|$ and $|t|$ denote the lengths of strings $s$ and $t$, respectively);
4. revert the string back to $s$.

The prefix function of a string $a$ is a sequence $p_1, p_2, \dots, p_{|a|}$, where $p_i$ is the maximum value of $k$ such that $k \lt i$ and $a[1..k]=a[i-k+1..i]$ ($a[l..r]$ denotes a contiguous substring of a string $a$ from a position $l$ to a position $r$, inclusive). In other words, it's the longest proper prefix of the string $a[1..i]$ that is equal to its suffix of the same length.

给你一个由小写拉丁字母组成的字符串 $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 \lt i$ 且 $a[1..k]=a[i-k+1..i]$ 的最大 $k$ 值（$a[l..r]$ 表示字符串 $a$ 中从位置 $l$ 到位置 $r$（含端点）的连续子串）。换言之，$p_i$ 是字符串 $a[1..i]$ 的最长真前缀，该前缀同时等于其长度相同的后缀。

The first line contains a non-empty string $s$ ($1 \le |s| \le 10^6$), consisting of lowercase Latin letters.

The second line contains a single integer $q$ ($1 \le q \le 10^5$) — the number of queries.

Each of the next $q$ lines contains a query: a non-empty string $t$ ($1 \le |t| \le 10$), consisting of lowercase Latin letters.

第一行包含一个非空字符串 $s$（$1 \le |s| \le 10^6$），由小写拉丁字母组成。

第二行包含一个整数 $q$（$1 \le q \le 10^5$）—— 查询次数。

接下来的 $q$ 行，每行包含一个查询：一个非空字符串 $t$（$1 \le |t| \le 10$），由小写拉丁字母组成。

For each query, print the values of the prefix function of a string $s+t$ on positions $|s|+1, |s|+2, \dots, |s|+|t|$.

对于每个查询，输出字符串 $s+t$ 在位置 $|s|+1, |s|+2, \dots, |s|+|t|$ 处的前缀函数值。