1252 : Karshilov's Matching Problem II

Description

Karshilov, as always, likes the string matching problem. This time, he gives a string \(S\) of length \(n\) and assigns a value to each prefix of \(S\). Specifically, the prefix of \(S\) with a length of \(i(1\le i\le n)\) is \(pre_i\) and its value is \(w_i\).

For any string \(t\), He defines a value function \(f(t) = \sum_{i=1}^n w_i \cdot occur(t,pre_i)\) based on the prefixes of given \(S\), where \(occur(t,pre_i)\) indicates the number of times \(pre_i\) occurs in the string \(t\). For example: \(occur (\texttt{heheh}, \texttt{heh}) = 2\) and \(occur(\texttt{hhh},\texttt{h}) = 3\).

Now, Karshilov has another string \(T\) of length \(n\). He will give you \(m\) queries. And each query will contains two integers \(l,r\), indicating to query the value of \(f(T[l,r])\), where \(T[l,r]\) represents a substring from the \(l\)-th character to the \(r\)-th character of the string \(T\) (that is, \(T_{l}T_{l+1}\cdots T_{r}\)).

Can you solve Karshilov’s queries like you did two years ago?

Input

The first line contains two integers, \(n,m(1\le n,m\le 150,000)\), indicating the length of string \(S\) (string \(T\)) and the number of queries.

The second line contains a string \(S\) of length \(n\).

The third line contains a string \(T\) with a length of \(n\).

The fourth line contains \(n\) integers, \(w_1,w_2,\cdots w_n\), where \(w_i(0\le w_i\le 10^8)\) is the value of \(pre_i\) .

For the next \(m\) lines, each line contains two integers \(l,r (1\le l\le r\le n)\), which means asking the value of \(f(T[l,r])\).

String \(S\) and \(T\) are both composed of lowercase letters.

Output

The output contains \(m\) lines. The \(i\)-th line contains an integer, indicating the answer of the \(i\)-th query.

Sample

8 5
abbabaab
aababbab
1 2 4 8 16 32 64 128
1 1
2 3
3 5
4 7
1 8
##CASE##
15 4
heheheheehhejie
heheheheheheheh
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
2 3
4 8
2 6
1 15

1
3
3
16
38
##CASE##
3
13
13
174

Hint

Source

Author

FUDAN