给定一个字符串 $s$ 和若干次查询。

每个查询包含一个字符串 $t$ 和一个整数 $k$。对于每个查询，确定 $s$ 中第 $k$ 次出现字符串 $t$ 的起始位置。如果 $t$ 在 $s$ 中出现的次数少于 $k$ 次，则输出 $-1$。

输入格式

第一行包含一个字符串 $s$ ($1 \le |s| \le 2 \cdot 10^5$)，即待查询的字符串。它仅由小写字母组成。

下一行包含一个整数 $q$ ($1 \le q \le 2 \cdot 10^5$)，表示后续查询的数量。

接下来的 $q$ 行，每行包含一个字符串 $t$ ($1 \le |t|$) 和一个整数 $k$ ($1 \le k \le |s|$)。这表示对 $t$ 在 $s$ 中第 $k$ 次出现位置的查询。字符串 $t$ 仅由小写字母组成。所有 $|t|$ 的总和不超过 $2 \cdot 10^5$。

输出格式

输出一个整数，表示 $t$ 在 $s$ 中第 $k$ 次出现的起始位置；如果 $t$ 在 $s$ 中出现的次数少于 $k$ 次，则输出 $-1$。$s$ 的第一个字符位置为 $1$。

样例

输入 1

abacabadabacaba
4
a 7
e 3
bac 2
abada 1

输出 1

13
-1
10
5