module mod_list
  implicit none
  private

  ! singly linked list
  type :: list_type
     type(list_type), pointer :: next
     integer :: value
  end type list_type

  interface assignment(=)
     module procedure assign
  end interface assignment(=)

  public :: list_type
  public :: new, delete,tail,  append, insert, remove, get
  public :: assignment(=)

contains

  ! assignment (initialize list with a given value)
  subroutine assign(a, b)
    implicit none
    type(list_type), pointer, intent(out) :: a
    integer, intent(in) :: b

    call delete(a)
    call new(a, value=b)

  end subroutine assign
  
! create a new node (pointer must be initialized by nullify() in advance)
  subroutine new(list, next, value)
    implicit none
    type(list_type), pointer, intent(out) :: list
    type(list_type), pointer, optional, intent(in) :: next
    integer, optional, intent(in) :: value

    if( associated(list) ) then
       write(*,*) 'Error in new'
    end if

    allocate(list)
    nullify(list%next)

    if( present(next) ) then
       list%next => next
    end if

    if( present(value) ) then
       list%value = value
    end if

  end subroutine new
  ! return the last node
  function tail(list) result(iter)
    type(list_type), pointer, intent(in) :: list
    type(list_type), pointer :: iter

    iter => list
    do while( associated(iter%next) )
       iter => iter%next
    end do

  end function tail

  ! append a single node at the last
  subroutine append(list, value)
    implicit none
    type(list_type), pointer, intent(in) :: list
    integer, intent(in) :: value

    type(list_type), pointer :: iter

    iter => tail(list)
    call new(iter%next, value=value)

  end subroutine append

  ! safely delete all the list contents
  subroutine delete(list)
    implicit none
    type(list_type), pointer, intent(inout) :: list

    type(list_type), pointer :: iter, temp

    if( .not. associated(list) ) then
       return
    end if

    iter => list
    do while( associated(iter%next) )
       temp => iter
       iter => iter%next
       deallocate(temp)
    end do

    nullify(list)

  end subroutine delete


  ! insert a node at a given index
  subroutine insert(list, index, value)
    implicit none
    type(list_type), pointer, intent(inout) :: list
    integer, intent(in) :: index
    integer, intent(in) :: value

    integer :: i
    type(list_type), pointer :: iter, prev, node

    if( index < 0 ) then
       write(*,*) 'Error: no such node'
       return
    end if

    ! find a node after which a new node is inserted
    nullify(prev)
    iter => list
    do i = 0, index-2
!!       if( .not. associated(iter%next) ) then
!!          write(*,*) 'Error: no such node iii'
!!          return
!!       end if
       prev => iter
       iter => iter%next
    end do

    ! create a new node
    nullify(node)
    call new(node, next=iter, value=value)

    if( .not. associated(prev) ) then ! first node
       list => node
    else
       prev%next => node
    end if

  end subroutine insert

  ! remove a node at a given index
  subroutine remove(list, index)
    implicit none
    type(list_type), pointer, intent(inout) :: list
    integer, intent(in) :: index

    integer :: i
    type(list_type), pointer :: iter, prev

!!    if( index < 0  ) then
!!       write(*,*) 'Error: no such node cc'
!!    end if

    ! find a node to be removed
    nullify(prev)
    iter => list
    do i = 0, index-2
!!       if( .not. associated(iter%next) ) then
!!          write(*,*) 'Error: no such node !!'
!!          return
!!       end if
       prev => iter
       iter => iter%next
    end do

    if( .not. associated(prev) ) then ! first node
       list => list%next
    else
       prev%next => iter%next
    end if

    deallocate(iter)

  end subroutine remove

  ! remove a node at a given index
  integer function get(list, index)
    implicit none
    type(list_type), pointer, intent(inout) :: list
    integer, intent(in) :: index

    integer :: i
    type(list_type), pointer :: iter, prev
    if( associated(list) ) then
       ! show contents
       iter => list
       !write(*, fmt='(i5, x)', advance='no') iter%value
       i = 0
       get =  iter%value
       if ( i == index ) return
       do while( associated(iter%next) )
          iter => iter%next
          get =  iter%value
          if ( i == index ) return
       end do
    end if
    return
!!    if( index < 0  ) then
!!       write(*,*) 'Error: no such node ',index
!!    end if

    ! find a node to be removed
    nullify(prev)
    iter => list
    do i = 0, index-1
       if( .not. associated(iter%next) ) then
          write(*,*) 'Error: no such node ',index
          return
       end if
       prev => iter
       iter => iter%next
    end do

    get = iter%value
  end function get

  
end module mod_list
program main
  use mod_list
  implicit none
  type arr_list
     integer :: N
     type(list_type), pointer :: root
  end type arr_list
  type(arr_list),allocatable :: data(:)
  integer :: num(97:122)
  integer :: N, Q
  character(len=500000) :: S
  character(:),allocatable :: tmp
  character(len=1) :: c,b,c2
  integer,allocatable :: tmp2(:)
  integer :: a
  integer :: i,j, l,r
  integer :: out
  read(*,*) N
  read(*,*) S
  read(*,*) Q
  allocate(data(97:122))
  allocate(tmp2(0:N-1))
  data(:)%N = 0
  do i = 1,N
     if (data(ichar(S(i:i)))%N == 0) then
        nullify( data(ichar(S(i:i)))%root  )
        data(ichar(S(i:i)))%root = i-1
     else
        call append (data(ichar(S(i:i)))%root, i-1  )
     end if
     data(ichar(S(i:i)))%N = data(ichar(S(i:i)))%N+1
  end do
  do i = 1, Q
     read(*,'(i1,1x,a,1x,a)') a,b,c
     if (a == 1) then
        backspace(5)
        !read(*,'(i1,1x,g0,1x,a)') a,j,c
        read(*,*) a,j,c
        c2 = S(j:j)
        call insert_delete(data,j-1,c,c2,tmp2,n)
        S(j:j) = c
     else
        backspace(5)
!        read(*,'(i1,1x,g0,1x,g0)') a,l,r
        read(*,*) a,l,r
        call count_char(data,l-1,r-1,out)
        write(*,'(i0)') out
        !deallocate(tmp)
     end if

  end do
contains
  subroutine insert_delete(data,key,c,c2,tmp,n2)
    implicit none
    type(arr_list),intent(inout) :: data(97:122)
    integer,intent(in) :: key ! key
    character,intent(in) :: c,c2 ! char
    integer,intent(in) :: n2
    integer :: tmp(0:n2-1)
    integer :: i,i2
    integer :: j
    integer :: n

    i = ichar(c)
    i2 = ichar(c2)
    if ( i /= i2) then ! insert and delete
       if ( data(i)%N > 0) then
          j = found_point(data(i)%root,data(i)%n, key)
          if ( j == data(i)%N) then ! out bound
             call append( data(i)%root, key)
             !
             ! delete
             !
             data(i2)%n = data(i2)%n - 1
             if ( data(i2)%n > 0) then
                j = found_point(data(i2)%root,n, key)
                call remove( data(i2)%root, j)
             else
                call delete( data(i2)%root )
             end if
             return
          else
             n = data(i)%n
             data(i)%n = data(i)%n + 1
             call insert( data(i)%root, j, key)
             !
             ! delete
             !
             data(i2)%n = data(i2)%n - 1
             if ( data(i2)%n > 0) then
                j = found_point(data(i2)%root,n, key)
                call remove( data(i2)%root, j )
             else
                call delete( data(i2)%root )
             end if
          end if
       else ! N == 0
          data(i)%N = data(i)%N + 1
          nullify(data(i)%root)
          data(i)%root =  key
          !
          ! delete
          !
          n = data(i2)%n
          data(i2)%n = data(i2)%n - 1
          if ( data(i2)%n > 0) then
             j = found_point(data(i2)%root,n, key)
             call remove( data(i2)%root, j)
          else
             call delete( data(i2)%root )
          end if
       end if
    end if
    return
  end subroutine insert_delete

  function found_point(a,n,key) result(ok)
    integer, intent(in) :: n
    type(list_type), pointer :: a
    integer,intent(in) :: key
    integer :: ng
    integer :: ok
    integer :: mid
    integer :: test
    ng = -1
    ok = n
    !do while( )
    test = 0
    do
       mid = (ok + ng)/2
       if (isOK(mid,key,a)) then
          ok = mid
       else
          ng = mid
       end if
       if (abs(ok-ng) <= 1) exit
    end do
  end function found_point

  function isOK (index, key,a ) result(out)
    type(list_type), pointer :: a
    integer,intent(in) :: index, key
    logical :: out
    if ( get(a,index) >= key) then
       out = .true.
    else 
       out = .false.
    end if
  end function isOK

  subroutine count_char(data,l,r,out)
    type(arr_list) :: data(97:122)
    integer :: l,r
    integer :: out
    integer :: N
    integer :: i, j, tmp
    out = 0
    do i = 97,122
       if ( data(i)%n > 0) then
          j = found_point(data(i)%root,data(i)%n,l)
          
          if ( j < data(i)%N) then
             if ( l<=get(data(i)%root,j) .and. get(data(i)%root,j) <= r) then
                out = out + 1
             end if
          end if
       end if
    end do
  end subroutine count_char
  
  subroutine count_char2(S,out)
    character(*) :: S
    integer :: out
    integer :: N
    integer :: i, tmp
    integer :: c(97:122)
    N = len_trim(S)
    c(97:122) = 0
    do i = 1,N
       tmp = ichar(S(i:i))
       c (tmp) = c(tmp) + 1
    end do
    out = count(c /=0)
  end subroutine count_char2
end program main
