Genomic Pairing Analysis

In the cutting-edge research lab at Helix Institute of Molecular Biology, scientists are analyzing strands of DNA to understand how nucleotides pair under spatial constraints.

You are part of a bioinformatics team tasked with analyzing a DNA sequence represented as a string of length $N$, composed of the nucleotides:

• Adenine ($A$)
• Thymine ($T$)
• Cytosine ($C$)
• Guanine ($G$)

As per Watson-Crick base pairing rules, $A$ pairs with $T$, and $C$ pairs with $G$.

Task

You are given a string of length $N$, made up of characters $A$, $T$, $C$ and $G$. We define the distance between the characters at positions $i$ and $j$ as being $\left| i-j \right|$. You are also given $Q$ queries of the form $l\ r$, where you have to count the number of $AT/CG$ pairs, such that they are at a distance between $l$ and $r$ in the string.

Input data

The input file consists of:

• a line containing integers $N$, $Q$.
• a line containing the $N$ character string $S$.
• $Q$ lines, the $j$-th of which consisting of the $2$ integers $l, r$.

Output data

The output file must contain the answer for each query on a separate line.

Constraints and clarifications

• $1 \le N \le 1 \ 000 \ 000$.
• $1 \le Q \le 1 \ 000 \ 000$.
• $S_{i} \in \{A, T, C, G\}$.
• $1 \le l \le r < N$ for each query.
• $TA$ and $GC$ are considered valid pairs.

Example

stdin

8 8
ATCGCGAT
1 1
2 2
3 3
4 4
5 5
6 6
7 7
1 7

stdout

5
0
1
0
1
0
1
8

Explanation

• The valid pairs of distance $1$ are the following: $\{(0, 1), (2, 3), (3, 4), (4, 5), (6, 7)\}$.
• The valid pairs of distance $2$ are the following: $\emptyset$.
• The valid pairs of distance $3$ are the following: $\{(2, 5)\}$.
• The valid pairs of distance $4$ are the following: $\emptyset$.
• The valid pairs of distance $5$ are the following: $\{(1, 6)\}$.
• The valid pairs of distance $6$ are the following: $\emptyset$.
• The valid pairs of distance $7$ are the following: $\{(0, 7)\}$.