21586번 - 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.

제한

힌트