题目背景

来源：https://www.gitlink.org.cn/thusaa/thuwc2018。

2018 清华大学信息学冬季体验营（THUWC 2018）D1T3。$\texttt{2s,0.5G}$。

---

我希望你明白，优秀的出题人是懒得写题目背景的。但是优秀的题目也可能需要让选手了解一些基本定义， 例如以下这些内容， 而熟练的算法竞赛选手几乎可以无视。

对于一个字符串 $S$， 我们定义 $\left|S\right|$ 表示 $S$ 的长度。接着，我们定义 $S_i$ 表示 $S$ 中第 $i$ 个字符，$S_{L,R}$ 表示由 $S$ 中从左往右数，第 $L$ 个字符到第 $R$ 个字符依次连接形成的字符串。特别的，如果 $L>R$，或者 $L \notin \left[1,\left|S\right|\right]$，或者$R \notin \left[1,\left|S\right|\right]$，则我们可以认为 $S_{L,R}$ 为空串。

我们再定义两个字符串 $A$ 和 $B$ 的加法， $A+B$ 为将 $B$ 字符串整体连接在 $A$ 的最后一个字符后面得到的大字符串。

例如，我们可以认为 aaaa $+$ bbbb $=$ aaaabbbb。

我们不难发现，上述定义的加法满足结合律，但不满足交换律。

最后，我希望你还能明白，字典序是什么。

为了让你明白字典序是什么，你还需要明白前缀是什么。我们说一个字符串 $A$ 是另一个字符串 $B$ 的前缀，当且仅当存在一个整数 $len$，使得 $A$ 与 $B_{1,len}$ 是完全相同的字符串。

对于两个不同的字符串 $A$ 和 $B$，如果 $A$ 是 $B$ 的一个前缀，则我们认为在字典序下， $A < B$； 如果 $B$ 是 $A$ 的前缀，则我们认为在字典序下，$B < A$。 否则，我们总能找到一个最小的 $i$， 使得 $A_i \neq B_i$， 如果 $A_i < B_i$， 则我们认为在字典序下，$A < B$，否则 $B > A$。

题目描述

现在给出一个长度为 $n$ 的字符串 $A$。 在此基础上，我会进行 $Q$ 次询问。

对于第 $i$（$1 \leq i \leq Q$）次的询问，我们会给出一个非空字符串 $B^{(i)}$， 并希望你找出一个最小的 $j$（$0 \leq j \leq n$）， 使得 $A_{1,j} + B^{(i)} + A_{j+1,n}$ 的字典序最小。 对于每个询问，你只需要输出你找到的这个 $j$ 即可。

输入格式

从标准输入读入数据。

第一行有两个用空格隔开的整数 $n, Q$， 分别代表字符串 $A$ 的长度，以及询问次数。

第二行给出一个长度为 $n$ 的字符串，表示字符串 $A$。

第三行到第 $Q+2$ 行， 每行会给出一个非空字符串， 第 $i$ 行所给出的字符串表示 $B^{(i-2)}$。

输出格式

输出到标准输出。

对于每个询问，请输出一行一个整数表示你所找到的最小的 $j$（$0 \leq j \leq n$）。

6 2
000001
00
01

0
5

提示

子任务

测试点编号	$n=$	$\sum \left\lvert B^{(i)}\right\rvert\le$	$Q\le$	其他约定
$1\sim 3$	$100$			无
$4\sim 8$	$10^3$
$9\sim 10$	$10^6$		$5\times 10^5$	$\lvert B^{(i)}\rvert=1$
$11\sim 14$	$3\times 10^5$	$5\times 10^5$	$3\times 10^5$	无
$15\sim 20$	$10^6$		$5\times 10^5$

对于所有测试数据，$1 \leq n \leq 10^6$，$1 \leq Q \leq 5 \times 10^5$，$1 \leq \sum \limits _{i=1}^{Q} \left|B^{(i)}\right| \leq 10^6$，输入的字符串全部由数字组成。

此外，我们保证，对于所有测试数据， $\sum \limits _{i=1}^{Q} \left|B^{(i)}\right|$ 不会小于其在该测试点对应上界的 $\frac{1}{10}$。