Typewriter again

Péter has an old typewriter where the keys (symbols) are arranged side by side, and some may appear multiple times. Before starting to type, a head must be placed at one of the positions located at the ends of the typewriter (these positions are marked with an underscore (_) in the typewriter’s description). The head can move left and right over the keys. There is also a button that, when pressed, sends the symbol currently under the head into the typewriter’s memory.

Moving to an adjacent key takes 1 second, while the time required to press the button is negligible. For each line of text provided, calculate the minimum number of time units required to transfer the text into the typewriter’s memory.

Input specification

The first line contains the typewriter: a string of length $K$, delimited by underscore (_) symbols (that is the total length is $K+2$). The next line contains the number of texts, $C$, followed by $C$ lines, each containing a string of at most length $L$, delimited by hash (#) symbols. The # symbols are not part of the text; they are included only to account for potential trailing spaces at the ends of the texts. Only lowercase letters of the English alphabet and space characters appear on the typewriter and in the text lines.

Output specification

The output should consist of $C$ lines, each containing the computed result. If it is not possible to input the given text into the typewriter’s memory, output $-1$.

Constraints

$1\le K \le 500$
$0\le L \le 300$
$0\le C \le 200$

Sample input 1

1. _abc _
2. 7
3. #abc#
4. #cba#
5. #abcba#
6. ##
7. #abababa#
8. #ab ab#
9. #abcd ab #

download as text file

Sample output 1

1. 3
2. 4
3. 5
4. 0
5. 7
6. 8
7. -1

download as text file