C - 串串

题目描述

定义 $occ(s,t)$ 为 $t$ 在 $s$ 中出现的次数，例如 $occ(ababa,aba)=2$ 。

定义 $S[l:r]$ 代表 $S_l,S_{l+1},\dots,S_r$ 连接形成的字符串。

现在给定长度为 $n$ 的串 $S,T$ 以及长度为 $n$ 的序列 $w$ 。

定义 $f(t)=\sum\limits_{i=1}^n w_i*occ(t,S[1:i])$ 。

现在有 $m$ 次询问，每次询问给定 $l,r$ ，你需要求出$f(T[l:r])$ 的值。

输入格式

第一行一个整数 $n,m$ ，分别代表串的长度，以及询问的个数。

第二行一个长度为 $n$ 的字符串表示 $S$ 。

第三行一个长度为 $n$ 的字符串表示 $T$ 。

第四行包含 $n$ 个整数，第 $i$ 个整数代表 $w_i$ 。

接下来 $m$ 行，每行包含两个整数 $l,r$ ，表示一次询问的信息。

输出格式

输出包含 $m$ 行，第 $i$ 行表示第 $i$ 次询问的答案。

样例

样例输入

8 5
abbabaab
aababbab
1 2 4 8 16 32 64 128
1 1
2 3
3 5
4 7
1 8

样例输出

1
3
3
16
38

数据范围

对于所有数据，$1\le n,m\le 4*10^5,1\le w_i\le 10^4,1\le l\le r\le n$ 。

子任务 1 ( 15% ) : $1\le n,m\le 300$ 。

子任务 2 ( 15% ) : $1\le n,m\le 3000$ 。

子任务 3 ( 20% ) ：$r=n$ 。

子任务 4 ( 20% ) ：$1\le n,m\le 50000$ 。

子任务 5 ( 20% ) ：$1\le n,m\le 2*10^5$ 。

子任务 6 ( 10% ) : 无特殊限制。