题目描述
给定字符串 s[1,n] ,第 i 个字符被赋予两个权值:左权值 wli 和右权值 wri 。
定义一个子串 s[l,r] 的左权值 vl(s[l,r]) 为: 其在原串中各个匹配的左端点的左权值 wl 和;右权值 vr(s[l,r]) 为: 其在原串中各个匹配的右端点的右权值 wr 和。这里 t 在 s 中所有的 匹配是 ∀1≤i≤j≤n,s[i,j]=t ,我们把这样的 i 和 j 分别叫做一个匹配的左右端点。
定义一个子串 s[l,r] 的复读程度是它的左权值与右权值的乘积,即 w(s[l,r])=vl(s[l,r])⋅vr(s[l,r]) 。
q 次查询 l1,r1,l2,r2 ,令 S={(l,r)∣r−l≥max ,即以 S 为所有满足 s\left[l_1, r_1\right] 为 s[l, r] 的前缀, s\left[l_2, r_2\right] 为 s[l, r] 的后缀的 (l, r) 的集合。求 \sum_{(l, r) \in S} w(s[l, r]) 。
由于答案很大,你只需要输出答案对 2^{64} 取模后的结果。
输入格式
第一行两个正整数 n, q ,表示字符串长度与查询次数。
第二行一个由小写字母构成的字符串 s 。
第三行 n 个整数 w l_i 表示左权值。
第四行 n 个整数 w r_i 表示右权值。
接下来 q 行,每行给出四个整数 l_1, r_1, l_2, r_2 ,表示一次查询。
输出格式
q 行,第 i 行输出第 i 次查询的答案对 2^{64} 取模后的结果。
样例数据
样例输入
6 5
ababcc
1 1 1 1 1 1
1 1 1 1 1 1
1 1 5 5
3 4 1 2
1 1 2 2
1 2 6 6
5 5 1 2
样例输出
4
9
9
4
0
子任务
保证 1 \leq n, q \leq 10^5, 0 \leq w l_i, w r_i < 2^{64}, 1 \leq l_1 \leq r_1 \leq n, 1 \leq l_2 \leq r_2 \leq n , s 仅有小写字母构成。
- subtask1(7pts):保证 n, q \leq 500 。
- subtask2(15pts):保证 n, q \leq 5000 。
- subtask3(12pts):保证 n \leq 5000 。
- subtask4(6pts): 保证 l_1=1 , 且对任意 2 \leq i \leq n ,有 s_1 \neq s_i 。
- subtask5(16pts):保证 s\left[l_1, r_1\right] 在 s 中最多出现 5 次。
- subtask6(21pts):保证 n, q \leq 5 \times 10^4 。
- subtask7(23pts):无特殊限制。