Lexicographically Smallest Insertion Position

You are given a string \( A \) of length \( n \). Then you are given \( Q \) queries. For the \( i\)-th query, a non-empty string \( B^{(i)} \) is provided. Your task is to choose an integer \( j \) (\( 0 \le j \le n \)) such that if you insert \( B^{(i)} \) into \( A \) at position \( j \) (i.e. form the string

[ F(j)= A_{1,j} + B^{(i)} + A_{j+1,n}, ]

where \( A_{1,j} \) denotes the first \( j \) characters of \( A \) (an empty string when \( j=0 \)) and \( A_{j+1,n} \) denotes the substring from position \( j+1 \) to \( n \) (an empty string when \( j=n \)), then \( F(j) \) is lexicographically minimum among all possible \( j \). If there are multiple positions yielding the lexicographically smallest string, output the smallest \( j \).

Note: The lexicographical comparison is the standard dictionary order.

inputFormat

The first line contains a non-empty string \( A \). The second line contains an integer \( Q \), the number of queries. Each of the following \( Q \) lines contains a non-empty string \( B^{(i)} \) representing the \( i\)-th query.

outputFormat

For each query, output a single integer \( j \) on a new line representing the chosen insertion position that produces the lexicographically smallest string.

sample

ab
3
b
a
z

1
0
2