有一次机灵鬼和学长可爱多打比赛， 可爱多不会做一道字符串题，机灵鬼做了很久终于做出来了，这是机灵鬼第一次做出可爱多不会的题。

可爱多觉得很丢人，于是准备研究字符串。可爱多精通 $\mathrm{kmp}$ 算法。$\mathrm{kmp}$ 算法的输入是一个字符串 $S$，该算法的核心是对每个 $i\in [1,n]$ 求出 ${\mathrm{next}}_i$，定义为： $${\mathrm{next}}_i=max\{x\mid 0\le x<i,S[1,x]=S[i-x+1,i]\}$$ 其中 $S[l,r]$ 表示字符串 $S$ 中第 $l$ 个到第 $r$ 个字符组成的子串，如果 $r<l$ 则为空串。

他发现，如果 $i$ 向 ${\mathrm{next}}_i$ 连边，最后会形成一棵以 0 为根的树。他还注意到，如果一个串的 “循环度” 比较高的话，这颗树所有点的深度和就会比较大，比如 $\mathrm{aaaa}$ 的树的深度和是 1+2+3+4，$\mathrm{abab}$ 的深度和为 1+1+2+2，而 $\mathrm{abcd}$ 的深度和只有 1+1+1+1，他给这个树的深度和取了一个名字，叫做 $\mathrm{next}$ 树深度和。所以，可爱多遇到一个串就想算出他的 ${\mathrm{next}}_{\mathrm{i}}$ 树深度和。

可爱多觉得仅仅算出一个串的 ${\mathrm{next}}_{\mathrm{i}}$ 树深度和并不能体现出他高超的水平。于是，他给每个位置设置了一个喜爱度 $w_i$，现在他想计算 $\sum _{i=1}^n{w}_i\times {\mathrm{dep}}_i$，我们称之为带权 ${\mathrm{next}}_i$ 树深度和。可爱多经过很多练习过后，对带权 ${\mathrm{next}}_{\mathrm{i}}$ 树深度和了如指掌，如果你告诉他一个长为 $n$ 的字符串 $S$，以及一个长为 $n$ 的数组 $W=\{w_1,w_2,\dots ,w_n\}$，他可以立马告诉你这个串的带权 ${\mathrm{next}}_{\mathrm{i}}$ 树深度。

现在机灵鬼给了可爱多一个长为 $n$ 的字符串 $S$ 供他研究，可爱多也设置好了 $n$ 个位置喜爱度。机灵鬼会多次取出字符串的一部分，即多次给出 $l,r$，他想让可爱多告诉他，当 $S^{\prime }=S[l,r]$，$W^{\prime }=\{w_l,w_{l+1},\dots ,w_r\}$ 时，带权 $\mathrm{next}$ 树深度和。为了避免答案过大，答案对 $2^{32}$ 取模。

机灵鬼不想太为难可爱多，于是他给出的字符串字符集为 $\{0,1\}$。可爱多算不出来就会觉得很丢脸，于是请你帮帮他。

输入格式

第一行两个正整数 $n,m$ 表示字符串长度和询问个数。

第二行一个字符串，保证字符集为 $\{0,1\}$。

第三行 $n$ 个正整数 $w_i$ 表示每个位置的喜爱度。

接下来的 $m$ 行，每行两个数 $l,r$ 表示一个询问。保证 $1\le l\le r\le n$。

输出格式

共 $m$ 行，每行一个整数表示答案。

样例一

input

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

22
28
15
42
17
48
29
8
9
22

样例二

见下发文件，这个样例满足子任务 5 的限制。

限制与约定

对于所有数据，有 $n,m\le 2\times {10}^5,1\le w_i\le {10}^9$。

时间限制：$6\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$