SP23507 RETRO - Retrovirus

小彼得是一名黑客和生物信息学家，他实现了自己迄今为止最伟大的黑客成就——他成功入侵了严密防守的生物技术武器部 (DBW) 数据库。这个部门被怀疑在过去制造了多种能够引发流行病的逆转录病毒。在这些秘密项目中，小彼得发现了一种可能引发新型、不治之症的逆转录病毒原型。 逆转录病毒将其用于攻击宿主细胞的所有遗传信息储存在一条单链 RNA（核糖核酸）中。RNA 链由一串核苷酸序列组成，这些核苷酸可以是腺嘌呤（A）、尿嘧啶（U）、胞嘧啶（C）或鸟嘌呤（G）。 小彼得了解到这个原型其实是一种已知逆转录病毒的变异版本，因此两种病毒在某些区域（子串）上可能会表现出高度“相似”。两个长度相同的区域之间的相似性被定义为相同位置上的核苷酸匹配的数量。例如，“ACAGU”和“AGAGA”的相似性为 3（在第 1、3、4 个位置上核苷酸匹配）。 小彼得已经找出了可能相似的区域——现在，你需要编写程序来计算它们的相似度。

输入的第一行是一个自然数 $N$，表示旧病毒和新病毒 RNA 链的长度。第二行和第三行分别是字符串 $RV_1$ 和 $RV_2$，它们代表相应的 RNA 链。 第四行是一个自然数 $Q$，代表需要回答的相似性查询的数量。接下来的 $Q$ 行每行包含三个自然数 $X$、$Y$ 和 $L$，表示需要计算 $RV_1$ 从第 $X$ 个位置开始、长度为 $L$ 的区域与 $RV_2$ 从第 $Y$ 个位置开始、长度为 $L$ 的区域之间的相似性。保证两个区域在各自的字符串中都至少可以延伸 $L$ 个字符。

对于每个查询，按顺序输出结果，每个结果占一行。

- $1 \le N \le 10^5$ - $1 \le Q \le 10^5$ - $1 \le X, Y \le N - L + 1$ - $1 \le L \le N$ **本翻译由 AI 自动生成**