Problem AI
Another Substring Query Problem

You are given a string $s$ and several queries.

Each query consists of a string $t$ and an integer $k$. For each query, determine the $k^{th}$ position in $s$ where a substring matching $t$ starts. If $t$ occurs fewer than $k$ times in $s$, print $-1$.

Input

The first line of input contains a single string $s$ ($1 \le |s| \le 2 \cdot 10^5$), which is the queriable string. It will consist only of lower-case letters.

The next line of input contains a single integer $q$ ($1 \le q \le 2 \cdot 10^5$), which is the number of queries that follow.

Each of the next $q$ lines contains a string $t$ ($1 \le |t|$) and an integer $k$ ($1 \le k \le |s|$). This represents a query for the $k^{th}$ occurrence of $t$ in $s$. The string $t$ will consist only of lower-case letters. The sum of all $|t|$’s will be $\le 2 \cdot 10^5$

Output

Output a single integer, which is the position of the start of the $k^{th}$ occurrence of $t$ in $s$, or $-1$ if $t$ occurs fewer than $k$ times in $s$. The first character in $s$ is at position $1$.

abacabadabacaba
4
a 7
e 3
bac 2
abada 1

13
-1
10
5