题目描述

本题包含多组测试。

特别注意：本题中，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]$ 为艾佛森括号），然后：

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		$200$			$10$	1
3	$3$	$10^5$	$2\times 10^9$	$A$	$15$	无
4				$B$	$5$
5				$C$	$15$
6				$D$	$20$
7				无	$30$	1,2,3,4,5,6

特殊性质 $A$：保证 $o\neq 2$。

特殊性质 $B$：保证字符串中的每一个字符都在 $26$ 个小写字母中独立均匀随机。

特殊性质 $C$：字符串中只含有 $\texttt{a}$。

特殊性质 $D$：保证 $type=0$。