孩童听了你的解答，恍然大悟。但她想要举一反三，于是又给了你一道类似的题目要求你求解。如果你解不出来，她将会非常生气，谁也不知道会有什么下场……

给定 $n$ 个小写字母字符串，第 $i$ 个字符串为 $s_i$。

定义一个字符串长为 $k$ 的前缀是它的前 $k$ 个字符组成的子串，长为 $k$ 的后缀是它的后 $k$ 个字符组成的子串，例如对字符串 kobayashibairuo，长为 3 的前缀为 kob，长为 5 的后缀为 airuo，长为 5 的前缀的长为 3 的后缀为 bay。

有 $q$ 个询问，每个查询给出三个整数 $x, y,z$，你需要求出对所有 $n$ 个字符串 $s_i(1\le i\le n)$ 的全体长度至少为 $z$ 的非空前缀里，有多少个前缀的后缀与 $s_x$ 的长为 $y$ 的前缀相等。

输入一行整数 $n(1 \le n \le 5\times 10^4)$，代表字符串数量。

接下来输入 $n$ 行，第 $i$ 行输入字符串 $s_i(1\le |s_i|\le 10^5)$。

接下来输入一行一个整数 $q(1 \le q \le 2\times 10^5)$。

接下来输入 $q$ 行，第 $i$ 行包括两个整数 $x, y(1\le x\le n,1\le y\le |s_x|,1\le z\le 10^5)$。

保证所有字符串长度之和不超过 $2\times 10^5$，且所有字符串仅有小写字母组成。

输出 $q$ 行，每行一个整数，代表询问的答案。

对第一个样例，与 $s_1$ 长为 $2$ 的前缀相等的只有 $s_3$ 长为 $8$ 的前缀的长为 $2$ 的后缀，与 $s_2$ 长为 $6$ 的前缀的长为 $2$ 的后缀。

对第二个样例，所有前缀的长为 $1$ 的后缀都与其相等，故 $3+4+5=12$。