← 返回题目列表

Codeforces · 472/G

G. 设计教程:增加约束

中文机器翻译题面 查看原题

有一种简单的方法来创建困难任务:将一个简单的问题作为查询,并尝试找到一种比暴力破解更快的算法。这类任务通常出现在OI竞赛中,并且通常涉及数据结构。

我们尝试创建一个任务,例如我们以“汉明距离问题”为例:对于两个长度相同的二进制字符串s和t,它们之间的汉明距离是对应符号不同的位置个数。例如,“00111”和“10101”之间的汉明距离为2(不同的符号用粗体标记)。

我们按以下方式使用汉明距离问题作为查询:给您两个字符串 a 和 b 以及几个查询。每个查询将是:两个字符串 ap1ap1 + 1...ap1 + len - 1 和 bp2bp2 + 1...bp2 + len - 1 之间的汉明距离是多少?

请注意,在这个问题中,字符串是从零开始的,即 s = s0s1... s|s| - 1.

输入

第一行包含字符串 a (1 ≤ |a| ≤ 200000)。第二行包含字符串 b (1 ≤ |b| ≤ 200000)。两个字符串的每个字符要么是“0”,要么是“1”。

第三行包含一个整数 q (1 ≤ q ≤ 400000) — 查询数量。以下 q 行中的每一行包含三个整数:p1、p2 和 len(0 ≤ p1 ≤ |a| - len;0 ≤ p2 ≤ |b| - len),这些数字表示当前查询的参数。

输出

输出 q 个整数 — 查询的答案。

示例

输入 #1

101010
11110000
3
0 0 3
2 3 4
5 7 1

输出 #1

1
1
0

输入 #2

10001010101011001010100101010011010
101010100101001010100100101010
5
0 0 12
3 9 7
6 4 15
12 15 10
13 3 20

输出 #2

5
4
3
5
13