Problem Description

This problem contains multiple test cases.

Special note: in this problem, the definition of border is different. For strings $s,t$, if there exists a prefix and a suffix of $s$ (they may be empty, and may also be $s$ itself) that are equal to $t$, then $t$ is a border of $s$.

There is a string $S$ of length $n$. We use the information on this string to elect the president.

Let $p_i$ denote the prefix of $S$ of length $i$. In particular, $p_0$ denotes the empty prefix (including the $0$-th position). Now there are $n+1$ candidates standing on these $n+1$ prefixes, indexed by $[0,n]$. Candidate $i$ corresponds to prefix $i$. Each person has a number of votes $a_i$ and a cost $w_i$.

A person whose number of votes is strictly more than half of the total votes can be elected president.

Initially, everyone is in the uncontrolled state. At each moment, any person $i$ who is uncontrolled and has been waiting all the time before can make one of the following three choices:

1. Perform one vote for $v$ operation: cast their own $a_i$ votes to person $v$ at a cost of $w_i$.
2. Perform one canvass votes for $v$ operation:
   • Spend $w_i$ to select person $v$, and it is required that $p_i$ is a border of $p_v$.
   • For all $j\in[0,n]$, if $p_v$ is a border of $p_j$, and $j$ is uncontrolled at this moment, then $j$ becomes controlled at the next moment, and all of their $a_j$ votes are cast to $i$ at a cost of $w_j$.
3. Wait for the next moment.

Each candidate hopes that no one else will become the president, and everyone is extremely smart. In particular, when operations overlap and cause one person's votes to need to be cast to multiple people, the overlapped person's votes can be cast independently to each of them and are all valid (you may think of their votes as splitting). Therefore, there may be multiple presidents.

You can intervene in this process. Specifically, at time $0$ you may operate on a candidate $x$, making $x$ perform one specified choice, and you may also fix all variables involved in that choice. After that, $x$ can no longer make any choices, and the remaining people must start choosing from time $1$. The cost of your intervention is the total cost of this choice made by $x$.

Votes $a$ and costs $w$ will change $q$ times.

Each change modifies one entry of $a$ or one entry of $w$. A vote count $a$ may become any positive integer, and a cost $w$ will only decrease or stay the same.

After each change, you need to find a person $x$ such that there exists a way for you to intervene on them so that they are guaranteed to become president, and the intervention cost is minimized. You only need to output this minimum cost.

It can be proven that such a person always exists.

This problem is forced online.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case:

One line contains three integers $n,q,type$, denoting the string length, the number of modifications, and whether it is forced online.

The next line contains a string $S$ of length $n$. It is guaranteed that $S$ contains only lowercase English letters.

The next $n+1$ lines each contain two integers $a_i,w_i$, in order describing the initial votes and costs of candidates $0$ to $n$.

The next $q$ lines each contain three integers $o',p',x'$. Let $lst$ be the absolute value of the previous output answer. Then $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]}$ (where $[x'\leq 0]$ is the Iverson bracket), and then:

1. When $o=1$, modify $a_p$ to $x$.
2. When $o=2$, modify $w_p$ to $w_p'=x$. It is guaranteed that $w_p\geq w_p'$.

Output Format

Output $q+1$ lines in total.

The first line outputs the minimum intervention cost in the initial state.

After that, output the minimum intervention cost after each modification, for a total of $q$ lines.

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

Hint

Sample #1 Explanation

For the first test case:

Consider the state before the first modification. There are $11$ votes in total, so being elected president requires $>5.5$ votes.

Intervene on candidate $0$, and choose the first option. After performing one vote for $0$ operation with cost $w_0=1$, candidate $0$ gets $6$ votes and directly meets the requirement for president. It can be proven that this is the minimum-cost answer.

After the first modification, there are $7$ votes in total, so being elected president requires $>3.5$ votes.

Intervene on candidate $1$, and choose the second option. After performing one canvass votes for $1$ operation, candidate $1$ will get $5$ votes, and the total cost is $-1+(-1)+2=0$. They directly meet the requirement for president. It can be proven that this is the minimum-cost answer.

For the third test case, after removing the forced-online encoding, the modification operations are:

• $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$.

Constraints

Please note the impact of constant factors on program efficiency.

This problem enables subtask bundling and subtask dependencies.

For $100\%$ of the data, $1\leq T\leq 2000$, $1\leq n\leq 10^5$, $0\leq q\leq 10^5$, $0\leq type\leq 1$, and it is guaranteed at any time that $1\leq a_i\leq 2\times 10^9$, $|w_i|\leq 2\times 10^9$.

It is guaranteed that the string contains only lowercase letters.

For any single modification, it is guaranteed that $o$ is $1$ or $2$, and $0\leq p\leq n$. When $o=1$, $1\leq x\leq 2\times 10^9$; when $o=2$, $0\leq |x|\leq 2\times 10^9$.

In particular, each entry in $w_i$ is monotone non-increasing during the operations.

Special property $A$: it is guaranteed that $o\neq 2$.

Special property $B$: each character in the string is independently and uniformly random among the $26$ lowercase letters.

Special property $C$: the string contains only $\texttt{a}$.

Special property $D$: it is guaranteed that $type=0$.

Translated by ChatGPT 5