题目描述

yz 是 Z 国的领导人，他规定每个地区的名字只能为 26 个小写拉丁字母的一个。由于地区数有可能超过 26 个，便产生了一个问题，如何辨别名字相同的地区？于是 yz 规定，一个地区的描述必须包含它的所有上级，且上级按次序排列。于是，一个地区的描述是一个字符串。比如说，一个地区的名字为 $c$，它的上级为 $b$，$b$ 的上级为 $a$，$a$ 没有上级，那么这个地区就描述为 $abc$。显然，这个描述同时包含了 $c$ 的上级 $b$ 和 $b$ 的上级 $a$ 的描述，分别为 $ab$ 和 $a$。

值得注意的是，每个地区最多有一个上级，同一上级的地区之间名字不同，没有上级的地区之间名字不同。

现在，yz 对外公布了 $n$ 个地区的描述，这些描述中包含了 Z 国所有地区的描述，并让你处理来访者的旅行问题。

现有 $m$ 对人访问这个国家，对于每对人，第一个人喜欢第 $i$ 个描述中的第 $j$ 个地区，设这个地区描述为 $s1$，第二个人喜欢第 $k$ 个描述中的第 $l$ 个地区，设这个地区描述为 $s2$。他们为了统一行程，决定访问描述为 $s$ 的地区（显然他们只关心地区的名字，并非是地区本身），设 $s$ 的长度为 $t$，$s$ 需要满足以下条件：

1. $t \leq j$ 且 $t \leq l$;
2. $s[1\cdots t] = s_1[j-t+1\cdots j]$，$s[1\cdots t] = s_2[l-t+1\cdots l]$（即 $s$ 为 $s_1$ 中 $1$ 到 $j$ 位与 $s_2$ 中 $1$ 到 $l$ 位的公共后缀）；
3. $t$ 最大化。

为了不使输出过大，你只需把这个字符串按照如下生成的 $26$ 进制数转成 $10$ 进制后 $\bmod 1000000007$ 后输出：a -> 0，b -> 1，……，z -> 25。

比如地区 cab 被编码成 $2 \times 26^2 + 0 \times 26^1 + 1 \times 26^0 = 1353$。

输入格式

第一行给定一个整数 $n$。

第 $2 \cdots n+1$ 行：每 $i+1$ 行给定一个字符串 $a[i]$,表示第 $i$ 个描述。

接下来一行一个整数 $m$。

接下来 $m$ 行:每行给定四个整数 $i,j,k,l$，字母含义与题目描述一致。

输出格式

共 $m$ 行，每行一个整数，表示答案字符串的编码。

2
aabb
babb
2
1 3 2 3
1 4 2 4

1
1

数据范围与提示

设这个国家地区总数数为 $tot$（注意：输入的字符串总长度可能超过 tot！）

对于 $30\%$ 的数据，满足 $tot, m, n \leq 100$；
对于 $50\%$ 的数据，满足 $tot, m, n \leq 1000$；
对于 $80\%$ 的数据，满足 $tot, m, n \leq 100000$；
对于 $100\%$ 的数据，满足 $tot, m, n \leq 1000000$。

保证输入文件不超过 20MB。