跳蚤国计算机协会 UOI 主席 “王中王” 认为 UOI 决赛所需要的经费过高。

比如隔壁黄蜂国的比赛，所有的题目均为大模型生成，但 UOI 决赛却需要请众多掌握三十二项能力的高手出面才能勉强凑齐比赛题目。

但是 UOI 比赛系列委员会早已制定了《大模型使用规章》，因此王中王决定以自己的名义出一些大模型生成的题目。

王中王发现，如果先让大模型生成一段毫无道理的内容，再从中截取一些有用的部分，就可以绕开《大模型使用规章》的检查。

现在王中王已经生成了一段长度为 $n$ 的字符串 $s$，而他将尝试进行 $q$ 次截取的尝试，每次有三个参数 $(x, y, z)$：

• 王中王将从 $s[x, n]$ 和 $s[y, n]$ 这两个后缀片段中提取相关性较大的内容，从而找出这段话有用的部分。
• 一些研究发现，跳蚤国的语言序顺不一定影响大体的含义，因此如果 $s[x, x + l - 1]$ 和 $s[y, y + l - 1]$ 循环同构，那么王中王就可以截取长度为 $l$ 的有效内容。
• 但王中王认为这些片段的重要性刚好是 $z$，所以王中王希望截取的长度和 $z$ 的绝对值之差最小。而如果有绝对值差相同的多种长度，那么越短越好。

现在王中王想知道每次截取中，最合适的长度是多少，如果没有办法截取，那么答案被认为是 $0$。

形式化题意：

给定长度为 $n$ 的字符串 $s$，定义 $s[l,r]$ 表示 $s$ 中第 $l$ 到第 $r$ 个字符组成的子串，$C(u,v)$ 表示 $u$ 和 $v$ 循环同构。

而 $u, v$ 循环同构当且仅当两者相等，或两者长度相等且存在 $c \in [1, |u| - 1]$ 使得 $u[c+1, |u|] + u[1, c]=v$，其中 $+$ 表示字符串拼接。

$q$ 次查询，每次给出 $x,y,z$，定义

$$ S=\{l\in[1,n-\max(x,y)+1]\mid C(s[x,x+l-1],s[y,y+l-1])\} $$

求出 $S$ 中与 $z$ 的差的绝对值最小的元素，若有多个，输出最小的那个。若 $S$ 为空集，输出 $0$ 。

输入格式

第一行三个正整数 $n,q,C$，其中 $C$ 表示子任务编号。

第二行一个字符串 $s$。

下面 $q$ 行，每行三个正整数 $x,y,z$。

输出格式

$q$ 行，每行一个整数表示答案。

8 6 1
ababaaba
1 4 4
2 4 3
6 7 2
5 7 2
5 5 3
3 4 5

3
2
2
0
3
5

样例二 $\sim$ 三

见“附件下载”。

数据范围

对于所有数据，$1\le n\le3\times 10^5$，$1\le q\le10^5$，$s$ 只包含小写字母，$1\le x,y\le n,1\le z\le n-\max(x,y)+1$。

对于最后 Subtask $4,5,6$，若你回答正确了前 $\min(q,50000)$ 个询问，可获得 $50\%$ 的部分分。请注意，若你只回答了一部分询问，你仍然需要输出 $q$ 个 int 范围内的整数才能得到部分分。

特殊性质 A：保证字符串中仅包含字符 $\texttt{a}$ 和 $\texttt{b}$，且每个字符独立等概率地在 $\texttt{a}$ 和 $\texttt{b}$ 中选择。保证该 Subtask 最多有 5 组数据。

特殊性质 B：$s$ 中不存在两个相邻子串相等，即不存在 $l,i$ 使得 $s[i-l,i-1]=s[i,i+l-1]$。

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

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

花鲜