object Main extends App {
  import scala.io.StdIn._
  val Array(n, q) = readLine.trim.split(' ').map(_.toInt)
  val str = readLine.trim.toCharArray
  val factor = (1 until n).filter(i ⇒ n % i == 0).toArray
  val countSubString = factor.map(f ⇒ Array.fill(f){Array.fill(26){0}})
  val countRepeating = factor.map(_ ⇒ 0)
  for (i ← str.indices) {
    for (j ← factor.indices) {
      countSubString(j)(i % factor(j))(str(i) - 'a') += 1
      if (countSubString(j)(i % factor(j))(str(i) - 'a') == n / factor(j)) {
        countRepeating(j) += 1
      }
    }
  }
  for (_ ← 0 until q) {
    readLine.trim.split(' ') match {
      case Array(p, to) ⇒
        val pos = p.toInt - 1
        var minLength = n
        for (j ← factor.indices) {
          countSubString(j)(pos % factor(j))(str(pos) - 'a') -= 1
          if (countSubString(j)(pos % factor(j))(str(pos) - 'a') == n / factor(j) - 1) {
            countRepeating(j) -= 1
          }
          countSubString(j)(pos % factor(j))(to.head - 'a') += 1
          if (countSubString(j)(pos % factor(j))(to.head - 'a') == n / factor(j)) {
            countRepeating(j) += 1
          }
          if (countRepeating(j) == factor(j)) {
            minLength = math.min(minLength, factor(j))
          }
        }
        str(pos) = to.head
        println(minLength)
      case _ ⇒ ???
    }
  }
}
