Mock CCC '22 2 S3 - Kaguya Wants to Analyze the Academy Anthem

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 5.0s
Memory limit: 1G

Problem type

Kaguya has heard that Miyuki has trouble singing the academy anthem. Upon deeper inspection, Kaguya suspects that the academy anthem has certain substrings that trip Miyuki up.

Given the academy anthem s and several query pairs (t_i, k_i), compute the kth 1-indexed position where the substring t appears in s.

Constraints

1 \le k_i \le |s| \le 2 \cdot 10^5

1 \le Q \le 2 \cdot 10^5

\sum |t_i| \le 2 \cdot 10^5

All strings only contain lowercase letters.

There are no subtasks in this problem. Each correct test case will award marks.

Input Specification

The first line contains the string s.

The next line contains an integer Q.

Each of the next Q lines contains a string t_i and an integer k_i, representing a query for the kth occurrence of t in s.

Output Specification

Output Q lines, the ith line containing the position of the k_ith occurrence of t_i in s, or -1 if there are fewer than k_i occurrences.

Sample Input 1

abacabadabacaba
4
a 7
e 3
bac 2
abada 1

Sample Output 1

13
-1
10
5

Comments

There are no comments at the moment.