https://www.acmicpc.net/problem/28329

# Foolish Lock

A contest for quickly solving locks is scheduled to be held in the KOI country. As a participant in this contest, you want to practice your lock-solving skills. The lock to be dealt with in this contest has a peculiar property, and it is named the "foolish lock."

The foolish lock can be represented by a string $S$ composed only of lowercase letters. With a single operation, you can choose a specific character of the lock and change it to an adjacent character in alphabetical order. For example, if the state of the foolish lock is "ioiaa," there are a total of $8$ possible operations:

* Change the 1st character from 'i' to 'h.'
* Change the 1st character from 'i' to 'j.'
* Change the 2nd character from 'o' to 'n.'
* Change the 2nd character from 'o' to 'p.'
* Change the 3rd character from 'i' to 'h.'
* Change the 3rd character from 'i' to 'j.'
* Change the 4th character from 'a' to 'b.'
* Change the 5th character from 'a' to 'b.'

The foolish lock has a unique property that allows it to be unlocked if the characters in the lock, when listed in order, are sorted in ascending alphabetical order. In other words, the $i$-th character of the foolish lock must not be alphabetically behind the $(i+1)$-th character. For example, 'aabbcc,' 'eel,' 'a,' 'zzzzz' are sorted in ascending alphabetical order. However, 'lee,' 'ccbbaa,' 'koi' are not sorted in ascending alphabetical order.

Given the state of a foolish lock as a string $S,$ the minimum number of operations needed to unlock this lock is called the difficulty of the lock. You have practiced hard to quickly calculate the difficulty of a string $S.$ Now, you want to make your practice more challenging with the following method:

Given the initial state of the foolish lock as $S$ and the length of $S$ as $N,$ you are given $Q$ update queries. Each query is given as an integer $i$ (between $1$ and $N$ inclusive) and a lowercase alphabet $c,$ meaning to change the $i$-th character of $S$ to $c.$ Queries must be applied in the given order. After outputting the difficulty of the initial foolish lock $S,$ you must output the difficulty of the modified foolish lock $S$ after each update query is completed.

# Input

The first line contains the string $S$.

The next line contains the number of queries, $Q$.

The next $Q$ lines each contain an integer $i$ and a lowercase alphabet $c$ separated by a space.

# Output

Print a total of $Q + 1$ integers. On the first line, output the difficulty of the foolish lock $S$. If $Q > 0$, then in the subsequent $Q$ lines, output the difficulty of the modified foolish lock $S$ after each update query.

# Constraints

- $S$ consists only of lowercase alphabets.
- Let $N$ be the length of $S$, $1 \le N \le 100,000$.
- $0 \le Q \le 100,000$
- $1 \le i \le N$
- $c$ is a lowercase alphabet.
- $c$ is guaranteed to be different from the $i$-th character of $S$ before the update.
- "Lowercase alphabet" refers to English lowercase letters, with the following 26 in order: abcdefghijklmnopqrstuvwxyz.

# Subtasks


"a,b,c,d" + (korean words) mean the string consists only of those characters and will only consist of those characters after updates.

# Samples

See the original statement for samples to copy