Sequential String

For each query independently, read s sequentially from its beginning; extra characters may be discarded and the selected characters may be rearranged. Find the length of the shortest prefix that must be read to form the query; output −1 if it cannot be formed. The original text mistakenly called the return value a substring; the body text and examples make it clear that reading starts from the beginning, not from an arbitrary sliding window.

输入格式

The first line contains the digit string s, the second line contains q, followed by q lines of length query; an empty query is written as 0 -. 1≤|s|≤100000, 1≤q≤20000, the total query length is 1..500000; characters are 0..9. The original text does not rule out occasional empty queries; this site supports them and returns 0.

输出格式

First output q, then output q shortest prefix lengths.

样例 1

输入：

064819848398
3
3 088
3 364
2 07

输出：

3
7 10 -1

样例 2

输入：

11
4
0 -
1 1
2 11
3 111

输出：

4
0 1 2 -1

样例 3

输入：

012
2
2 20
2 22

输出：

2
3 -1

样例说明

The answers to the three public examples are, in order: 3 7 10 -1; 4 0 1 2 -1; 2 3 -1. The examples were rechecked by independent enumeration, state search, or direct simulation.