『SpOI - R1』我看到了，谢谢你们

**本题包含多组测试。** **特别注意：本题中，border 的定义有所不同。对于串 $s,t$，若同时存在 $s$ 的一对前缀后缀（可空也可为 $s$ 本身）等于 $t$，则 $t$ 是 $s$ 的 border。** 有一个长度为 $n$ 的字符串 $S$。我们使用这个串上的信息来选举总统。 令 $p_i$ 表示 $S$ 的 $i$ 长前缀，特别地，$p_0$ 表示包含第 $0$ 位的空前缀。现在有 $n+1$ 位候选人站在这 $n+1$ 个前缀上，编号为 $[0,n]$，编号为 $i$ 的人对应前缀 $i$。每个人有一个票数 $a_i$ 和花费 $w_i$。 得票数量**严格**超过总票数一半的人可以当选总统。 初始时所有人都处于**未被控制**状态。每一个时刻，任何一个**未被控制**且**之前一直在等待**的人 $i$ 都可以做出三种选择之一： 1. 进行一次**对 $v$ 投票**操作：将自己的 $a_i$ 票花费 $w_i$ 的代价投给人 $v$。 2. 进行一次**对 $v$ 揽票**操作： - 花费 $w_i$ 选中人 $v$，需要满足 $p_i$ 是 $p_v$ 的一个 border。 - $\forall j\in[0,n]$，若 $p_v$ 是 $p_j$ 的一个 border，且 $j$ 在此时刻**未被控制**，则 $j$ 下一时刻变为**被控制**，他的 $a_j$ 票都花费 $w_j$ 投给 $i$。 3. 等待下一个时刻。 每个候选人都希望其他人不会成为总统，且都是绝顶聪明的。**特别地**，当他们的操作出现了交叉导致一个人的票需要投给多人时，被交叉者的票可以分别独立投出并都有效（你可以理解为他的票分裂了）。因此，总统可能有多个。 你可以干涉这个过程。具体来说，你可以在 $0$ 时刻操作一个候选人 $x$，让 $x$ 进行指定的一种选择，并钦定选择涉及的所有变量。$x$ 此后不能再做任何选择，剩下的人必须从 $1$ 时刻再开始选择。你干涉的代价就是 $x$ 这次选择的总花费。 票数 $a$ 和花费 $w$ 都会发生 $q$ 次变化。 每一次变化会改变票数 $a$ 中的某一项或是花费 $w$ 中的某一项。票数 $a$ 可能会变为任意正整数，花费 $w$ 只会变小或者不变。 在每次变化之后，你都需要找到这样一个人 $x$，满足你有一种干涉他的方案使得他一定可以成为总统，且你干涉的代价最小。你只需要输出这个最小代价。 可以证明一定存在这样的人。 本题**强制在线**。

第一行一个整数 $T$，表示数据组数。 对于每组数据： 一行三个整数 $n,q,type$，表示字符串长度、修改次数、是否强制在线。 接下来一行一个长度为 $n$ 的字符串 $S$。保证 $S$ 中只含有小写英文字母。 接下来 $n+1$ 行，每行两个整数 $a_i,w_i$，依次表示候选人 $0$ 到 $n$ 的初始票数和花费。 接下来 $q$ 行，每行三个整数 $o',p',x'$。设 $lst$ 表示上一次输出的答案的绝对值，则 $o\gets o'\oplus(type\times lst),p\gets p'\oplus(type\times lst),x\gets (|x'|\oplus(type\times lst))\times (-1)^{[x'\leq 0]}$（其中 $[x'\leq 0]$ 为[艾佛森括号](https://baike.baidu.com/item/%E8%89%BE%E4%BD%9B%E6%A3%AE%E6%8B%AC%E5%8F%B7/22361197)），然后： 1. $o=1$ 时，将 $a_p$ 修改为 $x$。 2. $o=2$ 时，将 $w_p$ 修改为 $w_p'=x$。保证 $w_p\geq w_p'$。

共 $q+1$ 行。 第一行输出在初始状态下你干涉的最小代价。 之后，在每次修改后输出你此时干涉的最小代价，共 $q$ 行。

3
2 1 0
aa
6 1
2 -1
3 2
1 0 2
19 0 0
happythbirthdayshun
1000000000 8
1000000000 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 0
1 1
1 0
1 0
5 6 1
acbac
1 3
2 4
1 -5
3 6
2 -3
3 1
11 10 12
9 13 108
8 12 8
10 9 0
6 1 4
4 7 1

1
0
17
9
8
-9
8
-4
-5
-5

#### 样例 #1 解释 对于第一组数据： 考虑第一次修改之前。全场共有 $11$ 票，则当选总统需要 $>5.5$ 票。 干涉 $0$ 号候选人，且选择第一种选择，使用 $w_0=1$ 的花费进行一次**对 $0$ 投票**操作后，$0$ 号候选人得到 $6$ 票，直接达到了总统要求，可以证明这是花费最小的答案。 第一次修改后，全场共有 $7$ 票，则当选总统需要 $>3.5$ 票。 干涉 $1$ 号候选人，且选择第二种选择，进行一次**对 $1$ 揽票**操作后，$1$ 号候选人将得到 $5$ 票，总花费为 $-1+(-1)+2=0$。他直接达到了总统要求，可以证明这是花费最小的答案。 对于第三组数据，去掉强制在线后的修改操作为： - $o=2,p=3,x=5$； - $o=1,p=5,x=100$； - $o=1,p=5,x=1$； - $o=2,p=1,x=-8$； - $o=2,p=5,x=0$； - $o=1,p=2,x=4$。 ### 数据范围 **请注意常数因子对程序效率的影响。** **本题开启子任务捆绑与子任务依赖。** 对于 $100\%$ 的数据，$1\leq T\leq 2000$，$1\leq n\leq 10^5$，$0\leq q\leq 10^5$，$0\leq type\leq 1$，且在任何时候都保证 $1\leq a_i\leq 2\times 10^9$，$|w_i|\leq 2\times 10^9$。 保证字符串中只含有小写字母。 对于任意一次修改，保证 $o$ 为 $1$ 或 $2$，且 $0\leq p\leq n$。在 $o=1$ 时，$1\leq x\leq 2\times 10^9$；$o=2$ 时，$0\leq |x|\leq 2\times 10^9$。 特别地，$w_i$ 中的每一项在被操作的过程中一定单调不递增。 | Subtask | $T\leq$ | $n,q\leq$ | $a_i,\lvert w_i\rvert \leq$ | 特殊性质 | 得分 | 子任务依赖 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $2000$ | $20$ | $10^5$ | 无 | $5$ | 无 | | 2 | $2000$ | $200$ | $10^5$ | 无 | $10$ | 1 | | 3 | $3$ | $10^5$ | $2\times 10^9$ | $A$ | $15$ | 无 | | 4 | $3$ | $10^5$ | $2\times 10^9$ | $B$ | $5$ | 无 | | 5 | $3$ | $10^5$ | $2\times 10^9$ | $C$ | $15$ | 无 | | 6 | $3$ | $10^5$ | $2\times 10^9$ | $D$ | $20$ | 无 | | 7 | $3$ | $10^5$ | $2\times 10^9$ | 无 | $30$ | 1,2,3,4,5,6 | 特殊性质 $A$：保证 $o\neq 2$。 特殊性质 $B$：保证字符串中的每一个字符都在 $26$ 个小写字母中独立均匀随机。 特殊性质 $C$：字符串中只含有 $\texttt{a}$。 特殊性质 $D$：保证 $type=0$。