题目描述

小 $Y$ 最不喜欢传统字符串。

给定一个长度为 $n$ 的字符串 $S$ 。

对于一个 $S$ 的子串 $S[l,r]$，定义 $endpos(S[l,r])=\{i|S[i-r+l,i]=S[l,r]\}$ 。若一个子串 $S[l,r]$ 是所有满足 $endpos(S[l,r])=endpos(S[i,j])$ 的 $S[i,j]$ 中长度最长的，我们就称 $[l,r]$ 为一个特征区间。

给出 $m$ 对特征区间，第 $i$ 对为 $[l_{1i},r_{1i}],[l_{2i},r_{2i}]$ 。

有 $q$ 次询问，第 $i$ 次给出一对特征区间 $[L_{1i},R_{1i}],[L_{2i},R_{2i}]$ ，你需要求出有多少个特征区间对$[a,b],[c,d]$ ，满足 :

• $S[L_{1i},R_{1i}]$ 是$S[a,b]$ 的后缀，$S[L_{2i},R_{2i}]$ 是 $S[c,d]$ 的前缀。
• 存在 $j\in [1,m]$， $S[l_{1j},r_{1j}]$ 是$S[a,b]$ 的后缀，$S[l_{2j},r_{2j}]$ 是 $S[c,d]$ 的前缀。

方便起见，请对 $2^{64}$ 取模 。

输入格式

第一行三个整数 $n,m,q$ 。

接下来一行表示一个字符串 $S$ 。

接下来 $m$ 行，每行四个整数 $l1_i,r1_i,l2_i,r2_i$ 。

接下来 $q$ 行，每行四个整数 $L1_i,R1_i,L2_i,R2_i$ 。

输出格式

$q$ 行，每行一个整数，方便起见，请对 $2^{64}$ 取模。

样例输入

10 5 5
abbcccaaab
1 9 1 10
4 5 9 9
1 4 1 6
1 2 7 7
4 5 1 4
1 9 1 10
1 6 1 9
4 5 1 10
1 6 1 8
1 4 1 3

样例输出

1
2
4
3
5

样例解释

懒得写了。

数据规模

• $20\%$，$1\leq n,m\leq 50$
• $20\%$，$1\leq n,m\leq 500$
• $20\%$，$1\leq n,m\leq 5000$
• $20\%$ ，$q\leq 5$

对于前三档，每一档的 $q$ 有梯度。

$1\leq n,m,q\leq 3\times 10^5$。