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

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

• 1 번째 문자를 \(i\) 에서 \(h\) 로 바꾼다.
• 1 번째 문자를 \(i\) 에서 \(j\) 로 바꾼다.
• 2 번째 문자를 \(o\) 에서 \(n\) 로 바꾼다.
• 2 번째 문자를 \(o\) 에서 \(p\) 로 바꾼다.
• 3 번째 문자를 \(i\) 에서 \(h\) 로 바꾼다.
• 3 번째 문자를 \(i\) 에서 \(j\) 로 바꾼다.
• 4 번째 문자를 \(a\) 에서 \(b\) 로 바꾼다.
• 5 번째 문자를 \(a\) 에서 \(b\) 로 바꾼다.

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

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

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

첫 번째 줄에 문자열 \(S\) 가 주어진다.

다음 줄에 쿼리의 수 \(Q\) 가 주어진다.

\(Q > 0\) 이라면, 다음 \(Q\) 개의 줄에 정수 \(i\) 와 알파벳 소문자 \(c\) 가 공백으로 구분되어 주어진다.

제약 조건

• \(S\) 는 알파벳 소문자로만 이루어져 있다.
• \(S\) 의 길이를 \(N\) 이라고 하였을 때, \(1 \le N \le 100 000\).
• \(0 \le Q \le 100 000\)
• \(1 \le i \le N\)
• \(c\) 는 알파벳 소문자이다.
• \(c\) 는 갱신 전 \(S\) 의 \(i\) 번째 문자와 다름이 보장된다.
• “알파벳 소문자”는 영문 알파벳 소문자를 의미하며, 순서대로 다음과 같은 26개가 있다:

\(abcdefghijklmnopqrstuvwxyz\) 

부분문제

1. (7점) \(Q = 0, N \le 5 000, S\) 는 문자 \(a, b\) 로만 이루어져 있다.
2. (6점) \(Q \le 10, S\) 는 문자 \(a, b\) 로만 이루어져 있으며, 각 갱신 이후에도 이것이 유지된다.
3. (5점) \(Q \le 10, S\) 는 문자 \(a, b, c\) 로만 이루어져 있으며, 각 갱신 이후에도 이것이 유지된다.
4. (4점) \(Q \le 10, S\) 는 문자 \(a, b, c, d, e\) 로만 이루어져 있으며, 각 갱신 이후에도 이것이 유지된다.
5. (3점) \(Q \le 10\)
6. (12점) \(S\) 는 문자 \(a, b\) 로만 이루어져 있으며, 각 갱신 이후에도 이것이 유지된다.
7. (10점) \(S\) 는 문자 \(a, b, c\) 로만 이루어져 있으며, 각 갱신 이후에도 이것이 유지된다.
8. (8점) \(S\) 는 문자 \(a, b, c, d, e\) 로만 이루어져 있으며, 각 갱신 이후에도 이것이 유지된다.
9. (45점) 추가 제약 조건이 없음.