这里：

原题面：

# [HEOI2012]旅行问题

## 题目描述

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$;

1：$s[1\cdots t] = s1[j-t+1\cdots j]$,$s[1\cdots t] = s2[l-t+1\cdots l]$；（（即 $s$ 为 $s1$ 中 $1$ 到 $j$ 位与 $s2$ 中 $1$ 到 $l$ 位的公共后缀））

2：$t$ 最大化。 为了不使输出过大，你只需把这个字符串按照如下生成的 $26$ 进制数转成 $10$ 进制后 $mod 1000000007$ 后输出:

a->0

b->1

.

.

.

z->25

比如地区 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

### 样例输入 #1

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

### 样例输出 #1

1 1

## 提示

###【样例说明】 

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

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

###【数据范围】 

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

对于 30%的数据，满足 tot，m，n<=100； 

对于 50%的数据，满足 tot，m，n<=1000； 

对于 80%的数据，满足 tot，m，n<=100000； 

对于 100%的数据，满足 tot，m，n<=1000000；

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

HEOI 2012 Day2 Task2

需要改为：

# [HEOI2012]旅行问题

## 题目描述

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] = s1[j-t+1\cdots j]$,$s[1\cdots t] = s2[l-t+1\cdots l]$；（（即 $s$ 为 $s1$ 中 $1$ 到 $j$ 位与 $s2$ 中 $1$ 到 $l$ 位的公共后缀））

3：$t$ 最大化。 为了不使输出过大，你只需把这个字符串按照如下生成的 $26$ 进制数转成 $10$ 进制后 $\bmod 1000000007$ 后输出:

$a->0$

$b->1$

.

.

.

$z->25$

比如地区 $cab$ 被编码成$ 2\times 26^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

### 样例输入 #1

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

### 样例输出 #1

1 1

## 提示

###【样例说明】 

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

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

###【数据范围】 

设这个国家地区总数数为 $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$。

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

HEOI 2012 Day2 Task2