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

小庆的作业答案是一个长度为 $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$；保证所有字符均为小写英文字母。

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

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