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

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

Sample Input 1 | Sample Output 1 |
---|---|

abacabadabacaba 4 a 7 e 3 bac 2 abada 1 |
13 -1 10 5 |