题目描述

给定一个字符串 $s$。

对于一个模式串 $w$，定义它的一个 $k$-扩展（$k$-rozpięcie） 为 $s$ 的一个连续子串（区间）$t$，满足 $w$ 在 $t$ 中作为连续子串出现了至少 $k$ 次。

这些出现位置可以互相重叠。

现在给定固定的字符串 $s$，以及若干组询问 $(k_i,w_i)$。对于每组询问，你需要求出 $w_i$ 的最短可能 $k_i$-扩展的长度。

如果在整个 $s$ 中都不足以出现 $k_i$ 次，则该询问无解。

输入格式

第一行包含一个仅由小写英文字母组成的字符串 $s$，满足：

$1\le |s|\le 10^5$。

第二行包含整数 $q$，表示询问数：

$1\le q\le 10^5$。

接下来 $q$ 行，第 $i$ 行包含一个整数 $k_i$ 和一个字符串 $w_i$，其中：

• $1\le k_i\le |s|$；
• 所有 $w_i$ 均只含小写英文字母；
• 所有询问中的模式串总长度满足 $\sum |w_i|\le 10^6$；
• 不会有两个询问使用完全相同的模式串 $w_i$。

输出格式

输出 $q$ 行。

第 $i$ 行输出模式串 $w_i$ 的最短 $k_i$-扩展长度。

如果这样的子串不存在，输出 -1。

样例

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

-1
2
-1
3
-1
1
-1

子任务