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.

Input

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, RV1 and RV2, 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 RV1 and the Yth position in RV2 should be calculated. It is guaranteed that this region can extend for at least L characters in both strings.

Output

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

Example

Input:
7
AUGCAAG
GGAUGCG
2
1 3 4
6 1 2 Output:
4
1

Explanation

Let A[i..j] be the substring of A starting on index i and ending on index j.

The first query asks for the similarity of RV1[1..4] = "AUGC" and RV2[3..6] = "AUGC", which is 4 (as this is a complete match).

The second query asks for the similarity of RV1[6..7] = "AG" and RV2[1..2] = "GG", which is 1 (as only the second index matches).

Constraints

  • 1 <= N <= 1000
  • 1 <= Q <= 106

Added by:PetarV
Date:2015-04-03
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Serbian Qualifications 2015 (Own problem)

hide comments
2020-02-28 07:33:05
precompute, prefix sum. etc
2015-04-07 15:19:05 Phong
I don't see why I'm getting WA for this :( I have already try various test case and till now my program works great :(

Re (PetarV): You're using the following command
ios_base::sync_with_stdio(false);
and after that you are combining cin and scanf in the same code. This usually does not work.
Even with that fix, your code will still get TLE, because your algorithm is too slow. Best of luck with solving!

Edited: Thank you very much! I have already worked out a DP solution but it got Core dump @@

Last edit: 2015-04-09 08:04:48
2015-04-05 00:31:10 Stefan Burgic
Solved in 20lines in Pascal :)
<Removed>

EDIT (PetarV): please, don't discuss the actual algorithm in here.
P.S. if it was so easy, you probably should've scored better on it in the actual qualifications. Have a go at solving SEGFAULT. :)

Last edit: 2015-04-05 14:50:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.