有一种简单的方法来创建困难任务:将一个简单的问题作为查询,并尝试找到一种比暴力破解更快的算法。这类任务通常出现在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