Kaguya has heard that Miyuki has trouble singing the academy anthem. Upon deeper inspection, Kaguya suspects that the academy anthem has certain substrings that trip Miyuki up.
Given the academy anthem and several query pairs
, compute the
th 1-indexed position where the substring
appears in
.
Constraints
All strings only contain lowercase letters.
There are no subtasks in this problem. Each correct test case will award marks.
Input Specification
The first line contains the string .
The next line contains an integer .
Each of the next lines contains a string
and an integer
, representing a query for the
th occurrence of
in
.
Output Specification
Output lines, the
th line containing the position of the
th occurrence of
in
, or
-1
if there are fewer than occurrences.
Sample Input 1
abacabadabacaba
4
a 7
e 3
bac 2
abada 1
Sample Output 1
13
-1
10
5
Comments