바보 자물쇠

문제

자물쇠를 빠르게 맞추는 대회가 KOI 나라에 개최될 예정이다. 이 대회에 참가하는 당신은 자물쇠를 맞추는 능력을 연습하려고 한다. 이번 대회에서 다룰 자물쇠는 그 성질이 특이하여, 바보 자물쇠 라는 이름이 붙어 있다.

바보 자물쇠는 알파벳 소문자로만 이루어진 문자열 $SS$ 로 표현할 수 있다. 당신은 한 번의 연산으로 자물쇠의 특정 문자를 골라, 알파벳 순서로 인접한 문자로 바꿀 수 있다. 예를 들어, 바보 자물쇠의 상태가 ioiaa 일 때, 당신에게 가능한 연산의 종류는 총 $88$ 가지이다:

• $11$ 번째 문자를 i 에서 h 로 바꾼다.
• $11$ 번째 문자를 i 에서 j 로 바꾼다.
• $22$ 번째 문자를 o 에서 n 로 바꾼다.
• $22$ 번째 문자를 o 에서 p 로 바꾼다.
• $33$ 번째 문자를 i 에서 h 로 바꾼다.
• $33$ 번째 문자를 i 에서 j 로 바꾼다.
• $44$ 번째 문자를 a 에서 b 로 바꾼다.
• $55$ 번째 문자를 a 에서 b 로 바꾼다.

바보 자물쇠는 순서대로 나열된 문자가 알파벳 오름차순으로 정렬되어 있을 경우 풀리는 특이한 성질을 가진다. 다시 말해, 바보 자물쇠의 $ii$ 번째 문자는 $i+1i+1$ 번째 문자보다 알파벳 순으로 뒤쳐지지 않아야 한다. 예를 들어, aabbcc, eel, a, zzzzz 는 알파벳 오름차순으로 정렬되어 있다. lee, ccbbaa, koi 는 알파벳 오름차순으로 정렬되어 있지 않다.

어떠한 바보 자물쇠의 상태가 문자열 $SS$ 로 주어졌을 때, 이 자물쇠를 풀기 위해 필요한 최소 연산 횟수를 자물쇠의 난이도 라고 하자. 당신은 문자열 $SS$ 의 난이도를 빠르게 계산하기 위해 열심히 연습하였다. 이제는 연습을 아래와 같은 방법으로 더 어렵게 하려고 한다.

초기 바보 자물쇠의 상태가 $SS$ 로 주어지고, $SS$ 의 길이를 $NN$ 이라고 할 때, 당신에게는 $QQ$ 개의 갱신 쿼리가 주어진다. 각 쿼리는 $11$ 이상 $NN$ 이하의 정수 $ii$ 와 알파벳 소문자 $cc$ 로 주어지는데, 이는 $SS$ 의 $ii$ 번째 문자를 $cc$ 로 바꾸라는 뜻이다. 쿼리는 주어진 순서대로 적용하여야 한다. 당신은 맨 처음 주어진 바보 자물쇠 $SS$의 난이도를 출력한 후, 각 갱신 쿼리가 끝날 때마다 변경된 바보 자물쇠 $SS$의 난이도를 출력하여야 한다.

입력

첫 번째 줄에 문자열 $SS$ 가 주어진다.

다음 줄에 쿼리의 수 $QQ$ 가 주어진다.

$Q>0Q\; >\; 0$ 이라면, 다음 $QQ$ 개의 줄에 정수 $ii$ 와 알파벳 소문자 $cc$ 가 공백으로 구분되어 주어진다.

출력

총 $Q+1Q\; +\; 1$ 개의 정수를 출력한다. 첫 번째 줄에는 바보 자물쇠 $SS$ 의 난이도를 출력한다. $Q>0Q\; >\; 0$ 이라면, 이후 $QQ$ 개의 줄에 걸쳐서 각 갱신 이후 변경된 바보 자물쇠 $SS$ 의 난이도를 출력한다.

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

2
2
1
2
1
2

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

3
4
3
5
4
5

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

16
16
16
26
26
31
17

zaire
1
5 r

38
25