또 다른 부분 문자열 질의 문제

문자열 $s$와 여러 질의가 주어진다.

각 질의는 문자열 $t$와 정수 $k$로 이루어진다. 각 질의마다 $s$에서 $t$와 일치하는 부분 문자열이 시작하는 위치 중 $k$번째 위치를 구한다. $t$가 $s$에서 $k$번 미만으로 나타나면 −1을 출력한다.

첫째 줄에 질의 대상 문자열 $s$가 주어진다. ($1 \le |s| \le 2 \cdot 10^5$) $s$는 소문자로만 이루어져 있다.

둘째 줄에 질의의 개수 $q$가 주어진다. ($1 \le q \le 2 \cdot 10^5$)

다음 $q$개 줄에는 각각 문자열 $t$와 정수 $k$가 주어진다. ($1 \le |t|$, $1 \le k \le |s|$) 이는 $s$에서 $t$가 나타나는 $k$번째 위치를 묻는 질의이다. $t$는 소문자로만 이루어져 있다. 모든 $|t|$의 합은 $2 \cdot 10^5$ 이하이다.

$s$에서 $t$가 나타나는 $k$번째 위치의 시작 지점을 나타내는 정수 하나를 출력한다. $t$가 $s$에서 $k$번 미만으로 나타나면 −1을 출력한다. $s$의 첫 번째 문자는 위치 1이다.