题目描述

约翰家里的门锁是一个密码锁，这个密码锁每一位都是小写字母。密码锁操作的方式是上下拨动。比如'b'经过一次拨动可以变成'a'或者'c','a'经过一次拨动可以变成'b'，'z'经过一次拨动可以变成'y'。

由于约翰家的密码锁有很多位，她没有设置具体的密码，而是规定：只要密码锁上呈现的密码串的字母是字典序非递减的，例如“aaabbb”,“c”，那么就可以开锁。

约翰想问问你，对于当前的密码串，她最少需要几次拨动可以开锁？

为了增加问题的难度，约翰又给了你Q次修改，每次修改某个位置的字符，对于每次修改之后的密码串，你需要回答她最少需要几次拨动可以开锁。

输入格式

第一行输入一个字符串S，S内仅包含小写字母。

第二行输入一个整数Q，代表修改的次数

其后Q行，每行一个正整数i一个字符c，中间用空格隔开。c是小写字母，i是$1\le i \le |N|$的整数。

输出格式

输出Q+1行，其中第1行是S串本身开锁需要的操作次数。

其后Q行每行一个整数，依次代表每次修改后，开锁需要的操作次数。

样例数据

input

ababba
5
1 b
3 b
2 a
2 b
5 a

output

2
2
1
2
1
2

input

acabed
5
1 c
2 a
3 d
4 c
5 a

output

3
4
3
5
4
5

input

acaykp
6
1 c
2 a
5 a
6 k
3 p
4 c

output

16
16
16
26
26
31
17

input

zaire
1
5 r

output

38
25

数据规模与约定

Subtask1(7pts) $Q=0,N \le 5000$,S中仅包含a，b两个字符

Subtask2(15pts) $Q\le 10$,S中最多包含a，b,c,d,e五个字符，修改的字符也在该限制内。

Subtask3(3pts) $Q\le 10$

Subtask4(30pts) S中仅包含a,b,c,d,e五个字符，修改的字符也在该限制内。

Subtask5(45pts) 无任何限制

对于所有的数据，$1\le |S| \le 100000,0 \le Q \le 100000$,S内仅包含小写字母。

时间限制：$2 \text {s}$

空间限制：$256 \text {MB}$