시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
6 초 1024 MB 17 10 8 53.333%

문제

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.

예제 입력 1

abacabadabacaba
4
a 7
e 3
bac 2
abada 1

예제 출력 1

13
-1
10
5