Protein Manufacturing
By Bruno Monteiro 
Brazil
By Bruno Monteiro Brazil
Proteins are biomolecules composed of one or more chains of amino acids. Each protein has its own sequence of amino acids which is specified by a sequence of nucleotides. The DNA is what stores this sequence and maintains the instructions on how to make proteins to keep cells, tissues and organisms functioning. Each DNA nucleotide contains one of the nitrogenous bases: adenine (A), guanine (G), cytosine (C) and thymine (T).
A promising area of bioinformatics is the synthesis of artificial genes, making it possible to “print” a completely new strand of DNA, allowing the creation of bacteria that synthesize or decompose certain materials, with applications being as diverse as possible. You are studying methods of synthesizing DNA and invented some proteins, and became curious to know if it would be possible to obtain this protein through small modifications of existing DNA.
Thus, with the description of a strand of DNA and the description of the protein, you want to check if parts of your protein exist in DNA. In order to do that, you want to know how many times certain substrings of the given protein appear in the DNA.
The first line is composed of two integers N and M (1 ≤ M ≤ N ≤ 105), the size of the DNA strand and the size of the protein respectively. The second line is composed of the N nucleotide DNA strand and the third is the protein composed of M nucleotides. A nucleotide is represented by a character that can be A, G, C or T.
Then follows the integer Q (1 ≤ Q ≤ 105), and follow Q lines, each one with a query, where each query consists of two integers A and B (1 ≤ A ≤ B ≤ M), which delimit the substring [A, B] of the protein.
For each query, print how many times the protein substring [A, B] appears on the DNA strand, in the same order as the input.
| Input Sample | Output Sample |
|
10 7 |
2 |