题目背景
我希望你明白，优秀的出题人是懒得写题目背景的。但是优秀的题目也可能需要让选手了解一些基本定义， 例如以下这些内容， 而熟练的算法竞赛选手几乎可以无视。
对于一个字符串 $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$ | $100$ | $100$ | 无 |
| $4\sim 8$ | $10^3$ | $10^3$ | $10^3$ | 无 |
| $9\sim 10$ | $10^6$ | $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$ | $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$，输入的字符串全部由数字组成。QOJ 中的 Hack 数据不受表格中 $n = $ 的限制。
此外，我们保证，对于所有测试数据， $\sum \limits _{i=1}^{Q} \left|B^{(i)}\right|$ 不会小于其在该测试点对应上界的 $\frac{1}{10}$ 。QOJ 中的 Hack 数据不受此限制。
在提交代码后将为你评测预测试数据并返回结果。本题的预测试数据包含 $5$ 个测试点，第 $i$ 个测试点满足表格中第 $i+1$ 行的数据规模限制。
注意：预测试数据的评测结果与最终评测结果没有关系。