← 返回题目列表

Codeforces · 963/D

D. 字符串频率

中文机器翻译题面 查看原题

给你一个字符串 $$$s$$$。您应该回答 $$$n$$$ 查询。第 $$$i$$$ 查询由整数 $$$k_i$$$ 和字符串 $$$m_i$$$ 组成。此查询的答案是字符串 $$$t$$$ 的最小长度,其中 $$$t$$$ 是 $$$s$$$ 的子字符串,并且 $$$m_i$$$ 作为子字符串在 $$$t$$$ 中至少出现 $$$k_i$$$ 次。

字符串的子串是字符串的连续字符段。

保证对于任意两个查询,这些查询中的字符串 $$$m_i$$$ 是不同的。

输入

第一行包含字符串 $$$s$$$ $$$(1 \leq \left | s \right | \leq 10^{5})$$$。

第二行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$)。

接下来的 $$$n$$$ 行包含一个整数 $$$k_i$$$ $$$(1 \leq k_i \leq |s|)$$$ 和一个非空字符串 $$$m_i$$$ — 编号为 $$$i$$$ 的查询参数,按此顺序。

输入的所有字符串均由小写英文字母组成。输入中所有字符串的长度总和不超过$$$10^5$$$。所有 $$$m_i$$$ 都是不同的。

输出

对于每个查询,在单独的行中输出其答案。

如果字符串$$$m_{i}$$$出现在$$$s$$$中少于$$$k_{i}$$$次,则输出-1。

示例

输入 #1

aaaaa
5
3 a
3 aa
2 aaa
3 aaaa
1 aaaaa

输出 #1

3
4
4
-1
5

输入 #2

abbb
7
4 b
1 ab
3 bb
1 abb
2 bbb
1 a
2 abbb

输出 #2

-1
2
-1
3
-1
1
-1