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

小庆的作业答案是一个长度为 $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\le L\le {10}^6$，$1\le n\le 10$，$1\le m\le 5\times {10}^4$，$1\le q\le {10}^6$；$1\le x_i\le n$，$1\le y_i\le m$，$1\le p_i\le L$；保证所有字符均为小写英文字母。

时间限制：$4\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$