题目描述

请在提交源代码前添加 #include "dna.h"。

Grace 是一名生物学家，在新加坡的一个生物信息学公司工作。她的一部分工作是分析不同有机体的 DNA 序列。DNA 序列是包含字符 A、T 和 C 的字符串。注意在本题中，DNA 序列不包含字符 G。

定义一次修改是把 DNA 序列中的两个元素交换位置的操作。例如，通过交换加粗的字符 A 和 C，一次修改可以把 ACTA 转化为 AATC。

两个序列的修改距离是把一个序列转化为另一个序列所用的最少修改次数。如果不能通过修改把一个序列转化为另一个序列，那么这两个序列的修改距离为 $-1$。

Grace 正在分析两个 DNA 序列 $a$ 和 $b$，每个都由 $n$ 个元素组成，下标从 $0$ 到 $n - 1$。你的任务是帮助 Grace 回答以下形式的 $q$ 个问题：子串 $a[x \ldots y]$ 和 $b[x \ldots y]$ 的修改距离是多少？这里，DNA 序列 $s$ 的子串 $s[x \ldots y]$ 定义为 $s$ 的下标从 $x$ 到 $y$（包括 $x$ 和 $y$）的连续字符序列。也就是说，$s[x \ldots y]$ 是序列 $s[x] \; s[x + 1] \; \ldots \; s[y]$。

---

实现细节

你要实现以下函数：

void init(string a, string b)

• $a$, $b$：长度为 $n$ 的字符串，表示两个待分析的 DNA 序列。
• 恰好调用此函数一次，且发生在任何对 get_distance 的调用之前。

int get_distance(int x, int y)

• $x$, $y$：待分析的子串的开始和结束下标。
• 此函数应返回子串 $a[x \ldots y]$ 和 $b[x \ldots y]$ 的修改距离。
• 恰好调用此函数 $q$ 次。

---

评测程序示例

评测程序示例按以下格式读取输入：

• 第 $1$ 行：$n \; q$
• 第 $2$ 行：$a$
• 第 $3$ 行：$b$
• 第 $4 + i$ 行（$0 \le i \le q - 1$）：$x \; y$，是第 $i$ 次调用 get_distance 的参数。

评测程序示例按以下格式打印你的答案：

• 第 $1 + i$ 行（$0 \le i \le q - 1$）：第 $i$ 次调用 get_distance 的返回值。

---

样例

输入：

6 3
ATACAT
ACTATA
1 3
4 5
3 5

输出：

2
1
-1

---

解释
考虑以下调用：

init("ATACAT", "ACTATA")

1. 如果评测程序调用 get_distance(1, 3)，那么该调用应返回 $a[1 \ldots 3]$ 和 $b[1 \ldots 3]$（也就是序列 TAC 和 CTA）之间的修改距离。通过 $2$ 次修改可以把 TAC 转化为 CTA：

   • TAC → CAT，
   • 然后是 CAT → CTA。
     无法通过比 $2$ 次更少的修改完成该转化。因此，该调用应返回 $2$。

2. 如果评测程序调用 get_distance(4, 5)，那么该调用应返回序列 AT 和 TA 之间的修改距离。通过一次修改可以把 AT 转化为 TA，而且显然至少需要一次。因此，该调用应返回 $1$。

3. 如果评测程序调用 get_distance(3, 5)，由于无法通过修改将序列 CAT 转化为 ATA，因此该调用应返回 $-1$。

---

数据范围与提示

对于所有数据：

• $1 \le n, q \le 100 \, 000$
• $0 \le x \le y \le n - 1$
• $a$ 和 $b$ 的每个字符都是 A、T 和 C 之一

子任务

子任务	分值	特殊限制
1	$21$	$y - x \le 2$
2	$22$	$q \le 500$，$y - x \le 1000$，$a$ 和 $b$ 的每个字符是 A 或 T
3	$13$	$a$ 和 $b$ 的每个字符是 A 或 T
4	$28$	$q \le 500$，$y - x \le 1000$
5	$16$	没有额外的约束条件