小重和小庆有时候会一起写作业。这天,小庆突然开始怀疑小重将自己的作业答案偷偷抄走了。
小庆的作业答案是一个长度为 $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}$