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.