CSG-CPC
Online Judge

# 1252 : Karshilov's Matching Problem II

Time Limit: 2 Sec     Memory Limit: 256 Mb     Submitted: 6     Solved: 6

## 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

FUDAN