题目描述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

出题Author

FUDAN

来源Source