T683915 decipher

乌尔里希组长在"暴雨"中采集到了一组数据并传输了过来, 留在拉普拉斯科算中心的哑谜和你负责接收这组数据

乌尔里希传回来的数据为一个长度为 $n$ 的字符串 $s$, 其只含有 $x$, $y$, $z$ 三种字母, 设 $s_i$ 为 $s$ 的第 $i$ 个字符 但不幸的是, 受"暴雨"影响, 部分数据产生了改变, 为了知道数据的改变过程, 哑谜决定暴力模拟改变的情景: 哑谜将进行 $m$ 操作, 每次会给出一个整数 $x$, 表示交换 $s_x$ 和 $s_{x+1}$ 两个字符 你需要在哑谜每次操作后破译当前的数据, 即统计出字符串 $s$ 中有多少个子序列为 $xyz$ ,第 $i$ 次破译得到的答案记为 $ans_i$ * 一个字符串 $t$ 是字符串 $s$ 的子序列，当且仅当可以从 $s$ 中删除若干个字符（可以为 $0$ 个），将剩下的字符按在 $s$ 中的顺序依次相接得到 $t$ 最后, 你需要告诉哑谜所有 $ans_i$ 的异或和

输入第一行为两个整数 $n$, $m$ 第二行为一个长度为 $n$ 的字符串 $s$ 第 $3$ ~ $m+2$ 行, 每行一个整数 $x$

一行一个整数表示你的答案

**样例2解释** : 初始时 $s=xxxyyzzz$ * 第一次操作交换 $s_4$ 和 $s_5$，此时 $s=xxxyyzzz$，$xyz$ 作为子序列出现了 $18$ 次。 第二次操作交换 $s_3$ 和 $s_4$，此时 $s=xxyxyzzz$，$xyz$ 作为子序列出现了 $15$ 次。 第三次操作交换 $s_5$ 和 $s_6$, 此时 $s=xxyxzyzz$，$xyz$ 作为子序列出现了 $12$ 次。 $18$ ^ $15$ ^ $12$ = $17$ ### 数据范围 | 测试点编号 | $n$ | $m$ | 特殊性质 | |:-:|:-:|:-:|:-:| | $1$ | $\le 3$ | $\le 10^3$ | - | | $2$, $3$ | $\le 10^3$ | $\le 10^3$ | $A, B$ | | $4$ ~ $6$ | $\le 10^4$ | $\le 10^4$ | $A, B$ | | $7$ ~ $9$ | $\le 10^6$ | $\le 10^2$ | $A$ | | $10$~ $12$| $\le 10^4$ | $\le 10^6$ | - | | $13$ ~ $20$ | $\le 10^6$ | $\le 10^6$ | - | 特殊性质 $A$ : 保证存在一个测试点只含有一个 $x$\ 特殊性质 $B$ : 保证存在一个测试点只含有一个 $y$ 保证对于所有的数据 $1\le x < n$ , $n \ge 3$ , $m \ge 1$ 下发的大样例 $1$ 满足特殊性质 $A$