No testdata at current.

题目描述

狗子研发了一款专门用于维护数列的软件。

初始时有一个长度为 $n$ 的数列，初始时光标在第 $k-1$ 个数和第 $k$ 个数之间。$k=1$ 即在整个序列的最左端，$k=n+1$ 即在整个序列的最右端。

狗子要在软件上操作 $m$ 次，第 $i$ 次操作为以下 $3$ 种之一：

• 将光标往左移动一个数，若原来光标在第 $c-1$ 个数和第 $c$ 个数之间，那么新的光标在第 $c-2$ 个数和第 $c-1$ 个数之间。
• 将光标往右移动一个数，若原来光标在第 $c-1$ 个数和第 $c$ 个数之间，那么新的光标在第 $c$ 个数和第 $c+1$ 个数之间。
• 在光标处插入一个数 $x$，若光标在第 $c-1$ 个数和第 $c$ 个数之间，就在第 $c-1$ 个数的后面插入 $x$，然后光标顺移至第 $c$ 个数和第 $c+1$ 个数之间。

每次操作完了后狗子都想要知道整个数列的最大子段和，即求整个数列 $a$ 的子区间 $[l,r]$ 使得 $\sum_{i=l}^ra_i$ 最大。

输入格式

第一行三个正整数依次为 $n,k,m$。

由于输入量过大，第二行为一个长度为 $n$ 的字符串。第 $i$ 位为一个小写字母 $c$ 来表示数列上第 $i$ 个数，此时第 $i$ 个数应为 $c-'m'$，即是小写字母的第几个减去 $13$。

第三行为一个长度为 $2m$ 的字符串。第 $2i-1$ 位为 $1/2/3$ 表示第 $i$ 操作是上面哪一种。若为 $1/2$ 那么第 $2i$ 位是一个没用的字符，否则第 $2i$ 位为一个小写字母 $c$ 来表示 $x$，此时 $x$ 的值应为 $c-'m'$，即是小写字母的第几个减去 $13$。

输出格式

为了减少输出量，设第 $i$ 次操作完的答案为 $ans_i$，允许选择空区间，所以一定为非负整数，那么需要输出：

$$ans_1\oplus (2\cdot ans_2)\oplus\cdots\oplus (i\cdot ans_i)\oplus ((i+1)\cdot ans_{i+1})\oplus \cdots \oplus (m\cdot ans_m). $$

样例输入输出

ex_a1.in

2 2 3 pn 3k203q ex_a1.ans

23 更多样例见下发文件。

样例解释

每次操作结束后的数列依次为 $\{3,-2,1\},\{3,-2,1\},\{3,-2,1,4\}$。

每次操作结束后的答案依次为 $3,3,6$。

数据范围与提示

对于全部数据，满足 $1\le n,m\le 10^7,1\le k\le n+1$

对于前 $60\%$ 的数据，满足 $1\le n,m\le 2000.$

对于前 $80\%$ 的数据，满足 $1\le n,m\le 10^5.$

时空限制

1s,1024MB