为了提升搜索引擎的关键词匹配度以加大访问量，某些网站可能在网页中无意义复读大量关键词。

你设计了一种方法量化评价一个文本（字符串 $s$）的“复读程度”：

字符串 $s$ 的下标从 $1\sim n$ 标号，第 $i$ 个字符被赋予两个权值：左权值 $wl_i$ 和右权值 $wr_i$ ，代表该位置的重要度。

定义一个子串 $s[l,r]$ 的左权值 $vl(s[l,r])$ 为：其在原串中各个匹配的左端点的左权值 $wl$ 和；右权值 $vr(s[l,r])$ 为：其在原串中各个匹配的右端点的右权值 $wr$ 和。这里 $t$ 在 $s$ 中所有的匹配是 $\forall 1 \le i \le j \le n,s[i,j]=t$，我们把这样的 $i$ 和 $j$ 分别叫做一个匹配的左右端点。

定义一个子串 $s[l,r]$ 的复读程度是它的左权值与右权值的乘积，即 $w(s[l,r])=vl(s[l,r])\cdot vr(s[l,r])$ 。

$s$ 的“复读程度”定义为所有子串复读程度的和，即：

$$\sum\limits_{i=1}^{|S|}\sum\limits_{j=i}^{|S|}w(s[i,j]).$$

根据网站文本抽样的复读程度限流，就可以达到打击无意义复读行为的目的。

隔壁生命科学实验室正在分析跳蚤的基因序列。他们对基因的复读情况很感兴趣，于是顺便把这个锅丢给了你。

基因片段可以被视作字符集为 $\{A,T,G,C\}$ 的字符串，你要求出给定的基因片段 $S$ 的复读程度。

有些时候，由于新的科学发现，某个位置 $u$ 的左权值 $wl_u$ 会相应修改为 $v$，修改过后你需要给出基因片段 $S$ 的新的复读程度。

由于答案很大，你只需要输出答案对 $2^{64}$ 取模后的结果。

输入格式

第一行一个正整数 $n$ 表示基因片段长度，一个整数 $m$ 表示操作次数。

第二行一个字符串 $S$ 表示基因片段。

第三行 $n$ 个整数 $wl_i$ 表示左权值。

第四行 $n$ 个整数 $wr_i$ 表示右权值。

接下来 $m$ 行，每行给出两个整数 $u_i,v_i$ ，表示将位置 $u_i$ 的左权值 $wl_{u_i}$ 修改为 $v_i$ 。

输出格式

第一行输出一个整数，表示初始时 $S$ 的复读程度对 $2^{64}$ 取模后的结果。

接下来 $m$ 行，第 $i$ 行输出第 $i$ 次操作后 $S$ 的复读程度对 $2^{64}$ 取模后的结果。

样例一

input

5 0
ATATA
1 2 3 4 5
1 2 3 4 5

output

550

样例二

input

10 5
ACGTAGCGAG
3 2 7 8 0 8 0 1 9 9
8 1 1 9 8 9 8 8 8 9
2 2
3 6
10 9
10 2
5 3

output

5427
5427
5260
5260
4504
4927

限制与约定

对于所有数据，满足 $1\leq n,m\leq 5\times 10^5,0\leq wl_i,wr_i,v_i< 2^{64},1\leq u_i\leq n$。

时间限制：$4\texttt{s}$

空间限制：$1\texttt{GB}$

注意常数因子带来的程序效率上的影响。

下载

样例数据下载