Background
I hope you understand that a good problem setter is too lazy to write a problem background. However, good problems may require contestants to understand some basic definitions, such as the following, which experienced algorithm competition contestants can almost ignore.
For a string $S$, we define $|S|$ as the length of $S$. Next, we define $S_i$ as the $i$-th character of $S$, and $S_{L,R}$ as the string formed by concatenating the characters of $S$ from the $L$-th position to the $R$-th position (counting from left to right). Specifically, if $L > R$, or $L \notin [1, |S|]$, or $R \notin [1, |S|]$, we consider $S_{L,R}$ to be an empty string.
We further define the addition of two strings $A$ and $B$ as $A+B$, which is the large string obtained by concatenating string $B$ to the end of string $A$.
For example, we can consider aaaa $+$ bbbb $=$ aaaabbbb.
It is not difficult to see that the addition defined above satisfies the associative law but does not satisfy the commutative law.
Finally, I hope you also understand what lexicographical order is.
To understand what lexicographical order is, you also need to understand what a prefix is. We say a string $A$ is a prefix of another string $B$ if and only if there exists an integer $len$ such that $A$ and $B_{1,len}$ are identical strings.
For two different strings $A$ and $B$, if $A$ is a prefix of $B$, then we consider $A < B$ in lexicographical order; if $B$ is a prefix of $A$, then we consider $B < A$ in lexicographical order. Otherwise, we can always find a minimum $i$ such that $A_i \neq B_i$. If $A_i < B_i$, then we consider $A < B$ in lexicographical order; otherwise, $B < A$.
Description
Given a string $A$ of length $n$, I will perform $Q$ queries.
For the $i$-th ($1 \leq i \leq Q$) query, we are given a non-empty string $B^{(i)}$, and we want you to find the minimum $j$ ($0 \leq j \leq n$) such that the lexicographical order of $A_{1,j} + B^{(i)} + A_{j+1,n}$ is minimized. For each query, you only need to output the $j$ you found.
Input
The first line contains two space-separated integers $n$ and $Q$, representing the length of string $A$ and the number of queries, respectively.
The second line contains a string of length $n$, representing string $A$.
From the third line to the $(Q+2)$-th line, each line contains a non-empty string, where the string given on the $i$-th line represents $B^{(i-2)}$.
Output
For each query, output a single integer on a new line representing the minimum $j$ ($0 \leq j \leq n$) you found.
Examples
Input 1
6 2
000001
00
01Output 1
0
5Subtasks
| Test Case ID | $n=$ | $\sum \left\lvert B^{(i)}\right\rvert\le$ | $Q\le$ | Other Constraints |
|---|---|---|---|---|
| $1\sim 3$ | $100$ | $100$ | $100$ | None |
| $4\sim 8$ | $10^3$ | $10^3$ | $10^3$ | None |
| $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$ | None |
| $15\sim 20$ | $10^6$ | $10^6$ | $5\times 10^5$ | None |
For all test data, $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$, and the input strings consist entirely of digits. Hack data in QOJ is not subject to the $n=$ limit in the table.
In addition, we guarantee that for all test data, $\sum \limits _{i=1}^{Q} \left|B^{(i)}\right|$ will not be less than $\frac{1}{10}$ of its upper bound corresponding to that test case. Hack data in QOJ is not subject to this restriction.
After submitting your code, the pretest data will be evaluated and the results returned. The pretest data for this problem contains $5$ test cases, where the $i$-th test case satisfies the data scale constraints of the $(i+1)$-th row in the table.
Note: The evaluation results of the pretest data have no relation to the final evaluation results.