Search for a substring in an ascii text.

Input

The input begins with the source text (having ascii characters except space) of n characters in a single line (1 <= n <= 100000). The following line has an integer t indicating the number of substrings to be searched one after the other (1 <= t <= 1000) followed by t substrings (having ascii characters except space) one in each single line. Substrings are of positive length not exceeding 100000.

Output

For each substring to be searched in the source text, print the index (0 <= index <= n-1) at which the substring begins the first time in the source text; print -1 if the the search is unsuccessful.

Example

Input:
ababcaabccaaa
4
a
d
abc
ababcaabccaaaxyz

Output:
0
-1
2
-1