UOJ Logo Universal Online Judge

UOJ

附件下载 统计

小重和小庆有时候会一起写作业。这天,小庆突然开始怀疑小重将自己的作业答案偷偷抄走了。

小庆的作业答案是一个长度为 $L$ 的字符串 $s$,由小写英文字母组成。

小重有一个 $n$ 行 $m$ 列的字符矩阵 $T$,矩阵中每一个元素都是一个小写英文字母。小庆怀疑小重把自己的答案以某种形式写在矩阵里了。

定义字符矩阵中一条可行路径为一条从一个起点开始,每次向右或向下走一步,不走出边界的路径。

将一条可行路径上经过的字符按顺序拼起来,可以得到一个字符串,称为这条路径对应的串。

小庆对小重的字符矩阵进行了共计 $q$ 次检测。每次检测时,小庆会选择一个坐标 $(x_i,y_i)$,和字符串 $s$ 中的一个下标 $p_i$。

小庆需要找出一个最大的 $k$,使得存在一条从 $(x_i,y_i)$ 开始的经过 $k$ 个点的可行路径,使得该路径对应的串是 $s_{p_i} s_{p_i+1} \cdots s_{p_i+k-1}$,即 $s$ 中第 $p_i$ 到第 $p_i + k - 1$ 号位置组成的串。

请帮助小庆快速得到检测结果吧。

输入格式

第一行,输入 $4$ 个正整数,依次表示 $L,n,m,q$。

第二行输入一个长度为 $L$ 的字符串,表示串 $s$。

接下来 $n$ 行,每行输入一个长度为 $m$ 的字符串,表示字符矩阵 $T$。

接下来 $q$ 行,每行 $3$ 个正整数,表示这一组询问的 $x_i,y_i,p_i$。

输出格式

输出 $q$ 行,每行一个数,表示对应询问的答案。

样例一

input

12 2 9 2
pubabapubaba
abapubono
dddddabap
1 4 1
1 1 4

output

7
9

样例二/三/四/五/六/七/八

见附件下载,它们分别对应子任务 1,2,3,4,5,6,7。

限制与约定

对于所有测试点,$1 \leq L \leq 10^6$,$1 \leq n \leq 10$,$1 \leq m \leq 5 \times 10^4$,$1 \leq q \leq 10^6$;$1 \leq x_i \leq n$,$1 \leq y_i \leq m$,$1 \leq p_i \leq L$;保证所有字符均为小写英文字母。

子任务编号 特殊性质 分值
1 $n \leq 2$ $8$
2 $n \leq 3$ $12$
3 $n \leq 4$ $28$
4 $L,m,q \leq 1000$ $6$
5 $L,m,q \leq 2 \times 10^4$ $10$
6 $n \leq 7,q \leq 5 \times 10^5$ $20$
7 $16$

时间限制:$4\texttt{s}$

空间限制:$1\texttt{GB}$