题目描述

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$ 行，每行一个整数，表示答案字符串的编码。

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

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