Minimum Insertion Operations to Duplicate String

You are given a string \(S = \overline{s_1s_2\dots s_n}\). Consider another string \(T\) which is initially equal to \(S\). You are allowed to perform the following operation any number of times:

Select any substring of \(S\) (i.e. a contiguous segment \(S[l\dots r]\)) and insert it at any position in \(T\).

Your goal is to transform \(T\) into \(\overline{s_1s_1s_2s_2\dots s_ns_n}\) (i.e. every character in \(S\) appears twice consecutively, preserving the order). Define \(f(S)\) as the minimum number of operations required to achieve this.

In addition, \(S\) will undergo \(q\) modifications. Each modification is described by an integer \(p\) and a character \(c\) meaning that \(s_p\) is changed to \(c\) (\(c\) is a lowercase letter). After the initial state and after each modification, you are to compute \(f(S)\).

---

Note: In each operation, you may choose any substring from the current \(S\). It turns out that the optimal strategy is always to duplicate either a single character or two consecutive characters. In fact, one can always achieve the target using exactly \(\lceil n/2\rceil\) operations since one may pair up adjacent positions (if possible) to reduce the number of operations. Therefore, for any string \(S\) of length \(n\), the answer is:

[ f(S) = \lceil n/2\rceil = \begin{cases} \frac{n}{2}, & \text{if } n \text{ is even},\ \frac{n+1}{2}, & \text{if } n \text{ is odd}. \end{cases} ]

Since the modifications do not change the length of \(S\), the answer depends only on \(n\); thus, for every state of \(S\), \(f(S)\) remains \(\lceil n/2\rceil\).

inputFormat

The first line contains the string \(S\) consisting of lowercase letters.

The second line contains an integer \(q\) indicating the number of modifications.

Each of the next \(q\) lines contains an integer \(p\) (1-indexed) and a lowercase letter \(c\), meaning that the character at position \(p\) of \(S\) is changed to \(c\).

Note that the length of \(S\) remains unchanged.

outputFormat

Output \(q+1\) lines. The first line should contain \(f(S)\) for the initial string. Then, for each modification, output a line with the value of \(f(S)\) after that operation.

sample

abc
2
2 d
3 e

2
2
2

</p>