;;; Utils (quoted from https://competitive12.blogspot.com/2020/03/common-lisp.html)


;; Read fixnum

(declaim (ftype (function * (values fixnum &optional)) read-fixnum))
(defun read-fixnum (&optional (in *standard-input*))
  (declare (inline read-byte)
           #-swank (sb-kernel:ansi-stream in))
  (macrolet ((%read-byte ()
               `(the (unsigned-byte 8)
                     #+swank (char-code (read-char in nil #\Nul))
                     #-swank (read-byte in nil 0))))
    (let* ((minus nil)
           (result (loop (let ((byte (%read-byte)))
                           (cond ((<= 48 byte 57)
                                  (return (- byte 48)))
                                 ((zerop byte) ; #\Nul
                                  (error "Read EOF or #\Nul."))
                                 ((= byte #.(char-code #\-))
                                  (setq minus t)))))))
      (declare ((integer 0 #.most-positive-fixnum) result))
      (loop
        (let* ((byte (%read-byte)))
          (if (<= 48 byte 57)
              (setq result (+ (- byte 48) (the (integer 0 #.(floor most-positive-fixnum 10)) (* result 10))))
              (return (if minus (- result) result))))))))

;; fast read-line

(defmacro buffered-read-line (&optional (buffer-size 30) (in '*standard-input*) (term-char #\Space))
  (let ((buffer (gensym))
        (character (gensym))
        (idx (gensym)))
    `(let* ((,buffer (load-time-value (make-string ,buffer-size :element-type 'base-char))))
       (declare (simple-base-string ,buffer)
                (inline read-byte))
       (loop for ,character of-type base-char =
             ,(if (member :swank *features*)
                  `(read-char ,in nil #\Newline) ; on SLIME
                `(code-char (read-byte ,in nil #.(char-code #\Newline))))
             for ,idx from 0
             until (char= ,character #\Newline)
             do (setf (schar ,buffer ,idx) ,character)
             finally (when (< ,idx ,buffer-size)
                       (setf (schar ,buffer ,idx) ,term-char))
             (return (values ,buffer ,idx))))))


;;; invoke child process

#-swank
(unless (member :child-sbcl *features*)
  (quit
    :unix-status
    (process-exit-code
      (run-program *runtime-pathname*
                   `("--control-stack-size" "128MB"
                     "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                     "--eval" "(push :child-sbcl *features*)"
                     "--script" ,(namestring *load-pathname*))
                                                                 :output t :error t :input t))))



;-------------------
; Write code here
;-------------------

(defun count-target (lst &optional (acc nil) (flag 0))
  (cond
    ((null (rest lst)) (reverse acc))
    (t
     (when (and (char= (first lst) #\A)
                (char= (second lst) #\C))
       (incf flag))
     (count-target (rest lst) (cons flag acc)))))

(defun calc-cum-sum (lst &optional (acc (make-array (1+ (length lst)))))
  (dotimes (i (length lst) acc)
    (setf (aref acc (1+ i)) (+ (first lst)
                               (aref acc i)))
    (pop lst)))



(defun solve (s queries)
  (declare (optimize speed))
  (let* ((a (count-target s))
         (cum (calc-cum-sum a)))
    (labels ((count-ac (queries cum &optional ans)
               (cond
                 ((null queries) (reverse ans))
                 (t
                  (count-ac (rest queries) cum (cons (- (aref cum (1- (rest (first queries))))
                                                        (aref cum (1- (first (first queries)))))
                                                     ans))))))
      (count-ac queries cum))))




(defun main ()
  (let ((n (read))
        (amount-of-query (read))
        (s (concatenate 'list (read-line)))
        (queries nil))
    (dotimes (i amount-of-query)
      (push (cons (read) (read)) queries))
    (let ((ans (solve s (reverse queries))))
      (dotimes (i amount-of-query)
        (fresh-line)
        (princ (first ans))
        (pop ans)))
    (fresh-line)))

(main)


Measured memory_bytes: 82660