在下山市停留的最后一天，为了纪念他们参加的最后一次 UOI，hehe 蚤决定和 he_____he 蚤一起去酒馆喝酒。

出人意料的是，他们在酒馆看到了孔乙己。在下单的时候，孔乙己凑了上来，对 hehe 蚤说：“你学过 OI 吗？” hehe 蚤点一点头。孔乙己说，“学过 OI，……我便考你一考。border 的四种求法，怎样做的？” hehe 蚤想，这本是字符串中极入门的题目，便懒懒的答他道，“不就是建 SAM 后扫描线树剖线段树吗？”孔乙己显出极高兴的样子，点头说，“对呀对呀！这题还有第二种做法，还可以求出基本子串字典，你知道吗？”

he_____he 蚤听到后起了兴致，反问孔乙己道：“你知道 border 的第五种求法吗？考你一考，这题怎样做的？”。he_____he 蚤边说边用手指蘸了水，在柜台上写下了题面。

但这下不仅孔乙己被难住了，连 hehe 蚤也陷入了沉思。你能帮他们解决 he_____he 蚤的题目吗？

题目描述

如果一个字符串 $t_1$ 是另一个字符串 $t_2$ 的前缀，同时也是 $t_2$ 的后缀，那么我们称 $t_1$ 是 $t_2$ 的一个 border（边界）。

例如，字符串 $\mathtt{\text{abacaba}}$ 的 border 有：$\mathtt{\text{a}}$, $\mathtt{\text{aba}}$, $\mathtt{\text{abacaba}}$。

为了展示 border 的第五种求法，he_____he 蚤给定了一个长度为 $n$ 的字符串 $s$ 和一个数组 $f_1,\dots ,f_n$。

如果一个字符串 $t$ 在 $s$ 中出现了至少一次，那么我们定义 $t$ 的价值为 $f_c$，其中 $c$ 是 $t$ 在 $s$ 中的出现次数。

例如，字符串 $\mathtt{\text{abacaba}}$ 中，$\mathtt{\text{aba}}$ 出现了两次，价值为 $f_2$。

现有 $q$ 次询问，每次询问会给出一个区间 $[l,r]$。对于每个询问区间 $[l,r]$，你需要输出字符串 $s_l{s}_{l+1}\cdots s_r$ 的所有 border 的价值之和。即，取出 $s$ 在区间 $[l,r]$ 内的所有字符，拼成一个字符串；找出该串的所有 border，求出每个 border 的价值，然后求和。

所有 $f_i$ 的值在输入中给出。

输入格式

第一行两个正整数 $n,q$ ，表示 $s$ 的长度与询问次数。

第二行一个由小写字母构成的字符串 $s$ 。

第三行 $n$ 个数 $f_1,f_2,\dots ,f_n$ 。

接下来 $q$ 行，每行两个正整数 $l,r$ ，表示一次查询。

输出格式

$q$ 行，每行一个正整数，表示每次查询的答案。

样例一

input

5 4
ababa
1 2 3 4 5
2 3
2 4
1 4
1 5

output

2
3
3
6

explanation

对 $l=1,r=5$ 的询问，三个 border 分别为 $\mathtt{\text{a}},\mathtt{\text{aba}},\mathtt{\text{ababa}}$ ，对应的在原串中的出现次数分别为 $3,2,1$ ，所以答案为 $f_3+f_2+f_1=3+2+1=6$ 。

样例二

见附件下载。该样例满足子任务 2 的限制。

样例三

见附件下载。该样例满足子任务 3 的限制。

数据范围

对于所有数据，保证 $1\le n,q\le 5\times {10}^5,1\le l\le r\le n,1\le f_i\le {10}^9$ ，保证 $s$ 由小写字母构成。

特殊性质 A：保证 $s$ 的每个字符均从 $\mathtt{\text{a}}$ 和 $\mathtt{\text{b}}$ 中等概率独立随机生成。

特殊性质 B：保证 $\mathrm{\forall }1\le i\le n,f_i=i$ 。

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

空间限制：$1200\mathtt{\text{MB}}$

后记

本在一旁慢慢喝酒的小 d 听到了 he_____he 蚤的题目，三下五除二就秒杀了，起身走过来教育了 hehe 蚤和孔乙己。

在欢声笑语中，这一次旅程终于画上了句点。也许他们中的每一个人都永远不会忘记这一天。