Description

现在给出一个长度为 $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$ 即可。

Input Format

从标准输入读入数据。

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

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

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

Output Format

输出到标准输出。

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

6 2
000001
00
01

0
5

Hint

子任务

对于所有测试数据，$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}$。