[HEOI2012] 旅行问题

题目描述

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$ 位的公共后缀。 2. $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

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

输出样例 #1

1
1

说明

### 样例解释 询问 $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}$。 HEOI2012 Day 2 Task 2