C. Karshilov's Matching Problem II
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Examples
Input
8 5
abbabaab
aababbab
1 2 4 8 16 32 64 128
1 1
2 3
3 5
4 7
1 8
Output
1
3
3
16
38
Input
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
Output
3
13
13
174