9649 - 旅行问题

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

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

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

现有 m 对人访问这个国家，对于每对人，第一个人喜欢第 i 个描述中的第 j 个地区，设这个地区描述为 s_1，第二个人喜欢第 k 个描述中的第 l 个地区，设这个地区描述为 s_2。他们为了统一行程，决定访问描述为 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\ (10^9+7) 后输出：

• a \to 0；
• b \to 1；
• ……
• z \to 25。

比如地区 \tt cab 被编码成 2\times26^2+0\times26^1+1\times26^0=1353。

第一行给定一个整数 n。

第 2\cdots n+1 行，每 i+1 行给定一个字符串 a_i，表示第 i 个描述。

接下来一行一个整数 m。

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

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

询问 1 中的公共后有 \tt ab 和 \tt b，但是没有 \tt ab 这个地区，只有 \tt b 地区，所以只能选择 \tt b 这个地区；

询问 2 中的公共后有 \tt abb，\tt bb 和 \tt b，但是没有 \tt abb 和 \tt bb 这两个地区，只有 \tt b 地区，所以只能选择 \tt b 这个地区。

数据范围及约定

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

• 对于 30\% 的数据，满足 1\le tot, m, n \le 100；
• 对于 50\% 的数据，满足 1\le tot, m, n \le 1000；
• 对于 80\% 的数据，满足 1\le tot, m, n \le 10^5；
• 对于 100\% 的数据，满足1\le tot, m, n \le 10^6。

保证输入文件不超过 20\text{MB}。

河北省选