SP23507 RETRO - Retrovirus

Little Petar, hacker and bioinformatician, has successfully achieved his greatest hacking feat to date - he successfully broken into the highly guarded database of the DBW (Department of Biotechnological Weaponry), which is suspected of creating many pandemic-causing retroviridae in the past. Among many secret projects, he has discovered a prototype of a brand-new kind of retrovirus, potentially capable of causing a new, incurable disease. Retroviridae store all their genetic information used for attacking the host cell in a single strand of ribonucleic acid (RNA). An RNA strand consists of a string of nucleotides, that may be either Adenine (A), Uracil (U), Cytosine (C) or Guanine (G). Petar found out that the prototype is actually a mutated version of a known retrovirus - as such, it is expected that there are regions (substrings) where these two viruses are highly "similar". The similarity of two regions of same length is defined as the number of indices where their nucleotides match; e.g. the similarity between "ACAGU" and "AGAGA" is 3 (the nucleotides match on the first, third and fourth position). Petar has identified potentially similar regions - it is now up to you to write the program to calculate how similar they actually are.

The first line of the standard input contains a natural number N, the length of the RNA strand of both the old and the new retrovirus. The second and third line contain two strings, RV $ _{1} $ and RV $ _{2} $ , representing their RNA strands. The fourth line contains a natural number Q, representing the number of similarity queries that need answering. Each of the following Q lines contains three natural numbers X, Y and L - this means that the similarity of the regions of length L starting from the Xth position in RV $ _{1} $ and the Yth position in RV $ _{2} $ should be calculated. It is guaranteed that this region can extend for at least L characters in both strings.

For each of the Q queries, output the answers in order, each one in a separate line of the output.