Mutating DNA

Grace is a biologist working in a bioinformatics firm in Singapore. As part of her job, she analyses the DNA sequences of various organisms. A DNA sequence is defined as a string consisting of characters "A", "T", and "C". Note that in this task DNA sequences do not contain character "G".

We define a mutation to be an operation on a DNA sequence where two elements of the sequence are swapped. For example a single mutation can transform "ACTA" into "AATC" by swapping the highlighted characters "A" and "C".

The mutation distance between two sequences is the minimum number of mutations required to transform one sequence into the other, or −1 if it is not possible to transform one sequence into the other by using mutations.

Grace is analysing two DNA sequences a and b, both consisting of n elements with indices from 0 to n − 1. Your task is to help Grace answer q questions of the form: what is the mutation distance between the substring a[x..y] and the substring b[x..y]? Here, a substring s[x..y] of a DNA sequence s is defined to be a sequence of consecutive characters of s, whose indices are x to y inclusive. In other words, s[x..y] is the sequence s[x]s[x + 1] ... s[y].

Implementation details

You should implement the following procedures:

void init(string a, string b)

• a, b: strings of length n, describing the two DNA sequences to be analysed.
• This procedure is called exactly once, before any calls to get_distance.

int get_distance(int x, int y)

• x, y: starting and ending indices of the substrings to be analysed.
• The procedure should return the mutation distance between substrings a[x..y] and b[x..y].
• This procedure is called exactly q times.

Example

Consider the following call:

init("ATACAT", "ACTATA")

Let's say the grader calls get_distance(1, 3). This call should return the mutation distance between a[1..3] and b[1..3], that is, the sequences "TAC" and "CTA". "TAC" can be transformed into "CTA" via 2 mutations: TAC → CAT, followed by CAT → CTA, and the transformation is impossible with fewer than 2 mutations.

Therefore, this call should return 2.

Let's say the grader calls get_distance(4, 5). This call should return the mutation distance between sequences "AT" and "TA". "AT" can be transformed into "TA" through a single mutation, and clearly at least one mutation is required.

Therefore, this call should return 1.

Finally, let's say the grader calls get_distance(3, 5). Since there is no way for the sequence "CAT" to be transformed into "ATA" via any sequence of mutations, this call should return −1.

Constraints

Do note that you DO NOT necessarily have to solve for the general case, but only for the subproblem defined by the following constraints:
* $1 \le n, q \le 100\,000$
* $0 \le x \le y \le n - 1$
* Each character of $a$ and $b$ is one of "A", "T", and "C".
* $q \le 500, y - x \le 1000$, each character of $a$ and $b$ is either "A" or "T".

Sample grader

The sample grader reads the input in the following format:

• line 1: n q
• line 2: a
• line 3: b
• line 4 + i (0 ≤ i ≤ q − 1): x y for the i-th call to get_distance.

The sample grader prints your answers in the following format:

• line 1 + i (0 ≤ i ≤ q − 1): the return value of the i-th call to get_distance.

You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution, then provide a complete implementation in C++17. You should correctly implement the routine(s) described in Implementation Details, without reading or writing anything directly from stdin or to stdout, as input and output are passed through the implemented routines. Assume your code will be run on the OFFICIAL grader, and do not add a main, a sample grader, or any other functionality unless it has been explicitly requested.
Put your final solution within a single code block: cpp <your code here>

Problem statement (Mutating DNA)

Grace is a biologist working in a bioinformatics firm in Singapore. As part of her job, she analyses the DNA sequences of various organisms. A DNA sequence is defined as a string consisting of characters "A", "T", and "C". Note that in this task DNA sequences do not contain character "G".

We define a mutation to be an operation on a DNA sequence where two elements of the sequence are swapped. For example a single mutation can transform "ACTA" into "AATC" by swapping the highlighted characters "A" and "C".

The mutation distance between two sequences is the minimum number of mutations required to transform one sequence into the other, or −1 if it is not possible to transform one sequence into the other by using mutations.

Grace is analysing two DNA sequences a and b, both consisting of n elements with indices from 0 to n − 1. Your task is to help Grace answer q questions of the form: what is the mutation distance between the substring a[x..y] and the substring b[x..y]? Here, a substring s[x..y] of a DNA sequence s is defined to be a sequence of consecutive characters of s, whose indices are x to y inclusive. In other words, s[x..y] is the sequence s[x]s[x + 1] ... s[y].

Implementation details

You should implement the following procedures:

void init(string a, string b)

• a, b: strings of length n, describing the two DNA sequences to be analysed.
• This procedure is called exactly once, before any calls to get_distance.

int get_distance(int x, int y)

• x, y: starting and ending indices of the substrings to be analysed.
• The procedure should return the mutation distance between substrings a[x..y] and b[x..y].
• This procedure is called exactly q times.

Example

Consider the following call:

init("ATACAT", "ACTATA")

Let's say the grader calls get_distance(1, 3). This call should return the mutation distance between a[1..3] and b[1..3], that is, the sequences "TAC" and "CTA". "TAC" can be transformed into "CTA" via 2 mutations: TAC → CAT, followed by CAT → CTA, and the transformation is impossible with fewer than 2 mutations.

Therefore, this call should return 2.

Let's say the grader calls get_distance(4, 5). This call should return the mutation distance between sequences "AT" and "TA". "AT" can be transformed into "TA" through a single mutation, and clearly at least one mutation is required.

Therefore, this call should return 1.

Finally, let's say the grader calls get_distance(3, 5). Since there is no way for the sequence "CAT" to be transformed into "ATA" via any sequence of mutations, this call should return −1.

Constraints

Do note that you DO NOT necessarily have to solve for the general case, but only for the subproblem defined by the following constraints:
* $1 \le n, q \le 100\,000$
* $0 \le x \le y \le n - 1$
* Each character of $a$ and $b$ is one of "A", "T", and "C".
* $q \le 500, y - x \le 1000$, each character of $a$ and $b$ is either "A" or "T".

Sample grader

The sample grader reads the input in the following format:

• line 1: n q
• line 2: a
• line 3: b
• line 4 + i (0 ≤ i ≤ q − 1): x y for the i-th call to get_distance.

The sample grader prints your answers in the following format:

• line 1 + i (0 ≤ i ≤ q − 1): the return value of the i-th call to get_distance.

Execution limits

Your solution will have 1.0 second(s) execution time and 2048 MB memory limit to solve each test case.

Starting code

Here's your starting code with some skeleton/placeholder functionality:

#include "dna.h"

void init(std::string a, std::string b) {
}

int get_distance(int x, int y) {
    return 0;
}

参考函数签名

#include "dna.h"

void init(std::string a, std::string b) {
}

int get_distance(int x, int y) {
    return 0;
}

请在 submission.cpp 中实现该函数（可 #include "problem.h" 获取题目提供的声明）。判题时你的代码会与题目提供的 grader 一起编译链接。

本题是函数题，由 grader 调用你实现的函数。

由 grader 打印判定结果，无需自行读写 stdin/stdout。

include "dna.h"

void init(std::string a, std::string b) {
}

int get_distance(int x, int y) {
return 0;
}