Election Intervention

This problem is about electing a president through an intervention in a complex voting process. You are given a string \(S\) of length \(n\). For each \(0 \le i \le n\), let \(p_i\) be the prefix of \(S\) of length \(i\) (with \(p_0\) being the empty prefix). There are \(n+1\) candidates numbered from 0 to \(n\). Candidate \(i\) stands on prefix \(p_i\) and has vote count \(a_i\) and cost \(w_i\>.

A candidate is declared president if his total votes strictly exceed half of the total votes, i.e. strictly more than \(\frac{\sum_{j=0}^{n}a_j}{2}\).

The election is conducted in several rounds. Initially all candidates are uncontrolled. At every moment, any candidate \(i\) (who is uncontrolled and has been waiting) may choose one of the following operations:

1. Vote for candidate \(v\): Candidate \(i\) spends \(w_i\) and all his \(a_i\) votes are transferred to candidate \(v\).
2. Absorb votes from candidate \(v\) (this operation is called "\"lǎn piào\""):
   • Candidate \(i\) may choose candidate \(v\) provided that \(p_i\) is a border of \(p_v\) (i.e. there exists a prefix and a suffix of \(p_v\) that equals \(p_i\); note that the border can be empty or can be \(p_v\) itself).
   • Then, for every candidate \(j\) (with \(0 \le j \le n\)) such that \(p_v\) is a border of \(p_j\) and who is currently uncontrolled, candidate \(j\) becomes controlled and his votes \(a_j\) (each costing \(w_j\)) are added to candidate \(i\) in the next moment.
3. Wait for the next moment.

All candidates are extremely clever; none wishes another to be president. Moreover, if operations cross such that one candidate's votes are split among several targets, all parts are counted independently.

You are allowed to interfere in this process. At time 0 you may choose one candidate \(x\) and force him to perform a specified operation with all parameters chosen by you. After this intervention, candidate \(x\) does not act any further, and the remaining candidates begin playing from time 1. The cost of your intervention is exactly the cost that candidate \(x\) spends on the forced operation.

Thereafter, the quantities \(a\) and \(w\) are subject to \(q\) updates. Each update changes one particular entry of \(a\) (to an arbitrary positive integer) or of \(w\) (to a value that is not larger than its current value). After each update, you must determine a candidate \(x\) for which there exists an intervention plan guaranteeing that \(x\) becomes president, and output the minimum possible intervention cost for that candidate. It is guaranteed that at least one such candidate always exists.

Note: In this problem the definition of a border is different. For strings \(s\) and \(t\), if there exists a pair of prefix and suffix of \(s\) (possibly empty or equal to \(s\) itself) that equals \(t\), then \(t\) is considered a border of \(s\).

This is an online problem.

inputFormat

The first line contains two integers (n) and (q), where (n) is the length of the string (S).

The second line contains the string (S) of length (n).

The next (n+1) lines each contain two integers (a_i) and (w_i) for (i = 0, 1, \ldots, n).

Then follow (q) lines, each describing an update in the following format:

  t x v

If (t = 1), update (a_x) to (v). If (t = 2), update (w_x) to (v).

outputFormat

For each update, output on a separate line the minimum intervention cost needed (i.e. the minimum (w_x) among all candidates (x) for which the sum of votes in the group controlled by (x) is strictly greater than (\frac{\text{total votes}}{2})).

sample

3 3
aba
3 10
2 5
1 7
4 8
1 1 1
2 0 4
1 3 2

5
4
4