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

给定 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。