题目描述
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 需要满足以下条件:
- t≤j,t≤l。
- s[1⋯t]=s1[j−t+1⋯j],s[1⋯t]=s2[l−t+1⋯l],即 s 为 s1 中 1 到 j 位与 s2 中 1 到 l 位的公共后缀。
- t 最大化。
为了不使输出过大,你只需把这个字符串按照如下生成的 26 进制数转成 10 进制后 mod (109+7) 后输出:
- a→0;
- b→1;
- ……
- z→25。
比如地区 cab 被编码成 2×262+0×261+1×260=1353。
输入格式
第一行给定一个整数 n。
第 2⋯n+1 行,每 i+1 行给定一个字符串 ai,表示第 i 个描述。
接下来一行一个整数 m。
接下来 m 行,每行给定四个整数 i,j,k,l,字母含义与题目描述一致。
输出格式
共 m 行,每行一个整数,表示答案字符串的编码。
提示
样例解释
询问 1 中的公共后有 ab 和 b,但是没有 ab 这个地区,只有 b 地区,所以只能选择 b 这个地区;
询问 2 中的公共后有 abb,bb 和 b,但是没有 abb 和 bb 这两个地区,只有 b 地区,所以只能选择 b 这个地区。
数据范围及约定
设这个国家地区总数数为 tot(注意:输入的字符串总长度可能超过 tot!)
- 对于 30% 的数据,满足 1≤tot,m,n≤100;
- 对于 50% 的数据,满足 1≤tot,m,n≤1000;
- 对于 80% 的数据,满足 1≤tot,m,n≤105;
- 对于 100% 的数据,满足1≤tot,m,n≤106。
保证输入文件不超过 20MB。
HEOI2012 Day 2 Task 2