Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 22 de Novembro
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #06]

[DAA 024] Letras distintas

Suponha que tem inicialmente uma string s constituída por letras minúsculas do alfabeto inglês {a, b, c, ..., z}. Uma substring s[a,b] da string s é uma subsequência contígua formada pelas letras s_a, s_ap1, ..., s_b. Por exemplo, "ritmo", "alg" e "gori" são substrings de "algoritmo", mas "gomo", "alri" ou "imo" não o são.

Neste problema vai receber uma série de queries, de ações a tomar, que podem ser de dois tipos diferentes:

Substituir uma letra numa dada posição de de s por outra letra (que altera a string para as queries a seguir)
Calcular o número de letras diferentes (distintas) que existem numa dada substring de s

O Problema

Dada uma string inicial s e um lista de queries como atrás descrito, a sua tarefa é indicar o número de letras diferentes para cada uma das queries que pedem o número de diferentes letras numa substring.

Input

Na primeira linha vem uma string s constituída unicamente por letras minúsculas do alfabeto inglês.

Na segunda linha bem um número Q indicando o número de queries a responder. Seguem-se Q linhas cada uma indicando uma querie num dos dois formatos seguintes:

1 pos c indica que deve substituir a letra na posição pos pela letra c, ou seja, s_pos=c
2 a b indica que deve calcular e escrever o número de letras diferentes na substring s[a,b]

Output

O output deve ter uma linha por cada query do tipo 2 com a resposta correspondente, ou seja o número de letras distintas na substring pedida.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ \|s\| ≤ 100 000		Tamanho da string s
1 ≤ Q ≤ 100 000		Número de queries
1 ≤ pos ≤ \|s\|		Posição da letra a substituir numa query de tipo 1
1 ≤ a ≤ b ≤ \|s\|		Posição inicial e final da substring a considerar numa query de tipo 2

Exemplo de Input

abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7

Exemplo de Output

3
1
2

Explicação do Input/Output

A string inicial é "abacaba"
1ª query: substring s[1,4]="abac", pelo que existem 3 letras diferentes (a, b e c)
2ª query: modificar 4ª letra para b, ou seja, a string passa a ser "abababa"
3ª query: modificar 5ª letra para b, ou seja, a string passa a ser "ababbba"
4ª query: substring s[4,6]="bbb", pelo que existe apenas uma letra (b)
5ª query: substring s[1,7]="ababbba", pelo que existem 2 letras diferentes (a e b)

Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto