给你一个字符串 $$$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