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 $s$ and several query pairs $(t_i,k_i)$, compute the $k$th 1-indexed position where the substring $t$ appears in $s$.

Constraints

$1\le k_i\le |s|\le 2\cdot {10}^5$

$1\le Q\le 2\cdot {10}^5$

$\sum |t_i|\le 2\cdot {10}^5$

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 $s$.

The next line contains an integer $Q$.

Each of the next $Q$ lines contains a string $t_i$ and an integer $k_i$, representing a query for the $k$th occurrence of $t$ in $s$.

Output Specification

Output $Q$ lines, the $i$th line containing the position of the $k_i$th occurrence of $t_i$ in $s$, or -1 if there are fewer than $k_i$ occurrences.

Sample Input 1

abacabadabacaba
4
a 7
e 3
bac 2
abada 1

Sample Output 1

13
-1
10
5