魔法咒语

题目描述

奶龙正在学习魔法，他有一个仅由小写字母组成的，长度为 $n$ 的魔法串 $S$，以及一个包含 $m$ 个魔法咒语的字典。

魔法串 $S$ 的每个位置都有一个魔力值 $V_i$。

奶龙有一个魔法队列 $Q$，他需要从左往右扫描魔法串 $S$，每次将一个字符 push 入队列。每次 push 字符后，奶龙可以选择将队首的若干字符 pop。每天结束时，奶龙必须确保队列中的内容是某个魔法咒语的前缀（即从队列前端到后端，能够依次匹配上某个魔法咒语的前缀。特别地，空队列是所有魔法咒语的前缀）。

如果在某个时刻，队列中的内容恰好是某个魔法咒语，奶龙就成功念出了这个咒语。

现在有 $q$ 个询问，每个询问要求奶龙回答：在扫描到第 $x_i$ 个位置后，念出过第 $y_i$ 个魔法咒语的位置的最大魔力值是多少。

输入格式

• 第一行：三个整数 $m$、$n$ 和 $q$，分别表示魔法咒语的数量、魔法串的长度以及询问的数量。
• 第二行：一个长度为 $n$ 的字符串，只包含小写字母，表示魔法串 $S$。
• 第三行：一个长度为 $n$ 的整数数组 $V$ ，表示魔法串 $S$ 每个位置的魔力值。
• 接下来 $m$ 行：每行一个字符串，表示一个魔法咒语。
• 最后是 $q$ 行，每行两个整数 $x_i$ 和 $y_i$，表示询问扫描到第 $x_i$ 个位置后，念出过第 $y_i$ 个魔法咒语的位置的最大魔力值。

输出格式

对于每个询问，输出一行，表示扫描到第 $x_i$ 个位置后，念出过第 $y_i$ 个魔法咒语的位置的最大魔力值。如果没有念出过该咒语，输出 $0$。

样例 #1

样例输入 #1

2 5 5
ababa
1 2 3 4 5
b
aba
1 1
3 1
3 2
5 1
5 2

样例输出 #1

0
2
3
4
5

提示

数据范围：

• $1 \leq m, q \leq 200000$
• $1 \leq n \leq 500000$
• 魔法咒语的长度之和小于等于 $500000$
• 魔力值 $V$ 在 unsigned 范围内

子任务

Subtask 1 10pts

• $m, q \leq 500$
• $n \leq 1000$
• 魔法咒语的长度和 $L \leq 1000$

Subtask 2 10pts

• $m \leq 4000$
• $q \leq 10000$
• $n \leq 20000$
• 魔法咒语的长度和 $L \leq 20000$
• 魔法咒语的长度均为 $5$

Subtask 3 15 pts

• $m, q \leq 10000$
• $n \leq 20000$
• 魔法咒语的长度和 $L \leq 20000$

Subtask 4 20pts

• 魔法咒语的长度均为 $5$

Subtask 5 45pts

无额外限制