Once, Clever-Guy and his senior, Cute-More, were competing. Cute-More couldn't solve a string problem, but after working on it for a long time, Clever-Guy finally solved it. This was the first time Clever-Guy had solved a problem that Cute-More could not.

Cute-More felt embarrassed and decided to study strings. Cute-More is proficient in the $\mathrm{kmp}$ algorithm. The input to the $\mathrm{kmp}$ algorithm is a string $S$, and the core of the algorithm is to compute $\mathrm{next}_i$ for each $i \in [1, n]$, defined as: \begin{equation} \mathrm{next}_i = \max\{x\mid 0 \le x < i, S[1,x]=S[i-x+1,i]\} \end{equation} where $S[l, r]$ denotes the substring of $S$ from the $l$-th to the $r$-th character, and is an empty string if $r < l$.

He discovered that if one draws an edge from $i$ to $\mathrm{next}_i$, it forms a tree rooted at 0. He also noticed that if a string has a high "cyclic degree," the sum of the depths of all nodes in this tree will be relatively large. For example, the depth sum for $\mathrm{aaaa}$ is 1+2+3+4, for $\mathrm{abab}$ it is 1+1+2+2, while for $\mathrm{abcd}$ it is only 1+1+1+1. He gave this sum a name: the $\mathrm{next}$ tree depth sum. Therefore, whenever Cute-More encounters a string, he wants to calculate its $\mathrm{next}_i$ tree depth sum.

Cute-More felt that simply calculating the $\mathrm{next}_i$ tree depth sum of a string did not demonstrate his superior skills. Thus, he assigned a "likability" $w_i$ to each position and now wants to calculate $\sum_{i=1}^n w_i\times \mathrm{dep}_i$, which we call the weighted $\mathrm{next}_i$ tree depth sum. After much practice, Cute-More became an expert on weighted $\mathrm{next}_i$ tree depth sums. If you give him a string $S$ of length $n$ and an array $W=\{w_1,w_2,\dots,w_n\}$ of length $n$, he can immediately tell you the weighted $\mathrm{next}_i$ tree depth sum of the string.

Now, Clever-Guy has given Cute-More a string $S$ of length $n$ to study, and Cute-More has already set the likability for the $n$ positions. Clever-Guy will repeatedly extract parts of the string, i.e., he will provide $l, r$ multiple times, and he wants Cute-More to tell him the weighted $\mathrm{next}$ tree depth sum when $S'=S[l,r]$ and $W'=\{w_l,w_{l+1},\dots,w_r\}$. To avoid excessively large answers, the result should be taken modulo $2^{32}$.

Clever-Guy does not want to make things too difficult for Cute-More, so the character set of the string he provides is $\{0,1\}$. If Cute-More cannot calculate it, he will feel very embarrassed, so please help him.

Input

The first line contains two positive integers $n$ and $m$, representing the string length and the number of queries.

The second line contains a string, guaranteed to have a character set of $\{0,1\}$.

The third line contains $n$ positive integers $w_i$, representing the likability of each position.

The next $m$ lines each contain two integers $l$ and $r$, representing a query. It is guaranteed that $1 \le l \le r \le n$.

Output

Output $m$ lines, each containing an integer representing the answer.

Examples

Input 1

10 10
1110110001
3 1 4 1 5 9 2 6 5 3 
6 9
1 5
4 6
5 10
6 8
3 9
7 9
9 10
6 6
6 9

Output 1

22
28
15
42
17
48
29
8
9
22

Input 2

(See the provided file; this sample satisfies the constraints of Subtask 5.)

Constraints

For all data, $n, m \le 2\times 10^5$ and $1 \le w_i \le 10^9$.