CF472G.Design Tutorial: Increase the Constraints

There is a simple way to create hard tasks: take one simple problem as the query, and try to find an algorithm that can solve it faster than bruteforce. This kind of tasks usually appears in OI contest, and usually involves data structures.

Let's try to create a task, for example, we take the "Hamming distance problem": for two binary strings s and t with the same length, the Hamming distance between them is the number of positions at which the corresponding symbols are different. For example, the Hamming distance between "00111" and "10101" is 2 (the different symbols are marked with bold).

We use the Hamming distance problem as a query in the following way: you are given two strings a and b and several queries. Each query will be: what is the Hamming distance between two strings _a__p_1_a__p_1 + 1..._a__p_1 + len - 1 and _b__p_2_b__p_2 + 1..._b__p_2 + len - 1?

Note, that in this problem the strings are zero-based, that is s = _s_0_s_1... s|s| - 1.

有一种简单的方法可以构造难题：以一个简单问题作为查询，然后尝试设计一种比暴力算法更快的算法来解决它。这类题目通常出现在信息学奥林匹克竞赛（OI）中，且通常涉及数据结构。

我们来尝试构造一道题目。例如，选取“汉明距离问题”：对于两个等长的二进制字符串 $s$ 和 $t$，它们之间的汉明距离定义为对应位置上字符不同的位置个数。例如，“00111”与“10101”的汉明距离为 2（不同的字符用粗体标出）。

我们将汉明距离问题作为如下形式的查询：给定两个字符串 $a$ 和 $b$，以及若干查询。每个查询的形式为：字符串 $a_{p_1}a_{p_1+1}\dots a_{p_1+\text{len}-1}$ 与字符串 $b_{p_2}b_{p_2+1}\dots b_{p_2+\text{len}-1}$ 之间的汉明距离是多少？

注意，本题中字符串采用从零开始的索引方式，即 $s = s_0s_1\dots s_{|s|-1}$。

The first line contains a string a (1 ≤ |a| ≤ 200000). The second line contains a string b (1 ≤ |b| ≤ 200000). Each character of both strings is either "0" or "1".

The third line contains an integer q (1 ≤ q ≤ 400000) — the number of queries. Each of the following q lines contains three integers: _p_1, _p_2 and len (0 ≤ _p_1 ≤ |a| - len; 0 ≤ _p_2 ≤ |b| - len), these numbers denote the parameters of the current query.

第一行包含一个字符串 $a$（$1 \le |a| \le 200000$）。第二行包含一个字符串 $b$（$1 \le |b| \le 200000$）。两个字符串的每个字符均为 "0" 或 "1"。

第三行包含一个整数 $q$（$1 \le q \le 400000$）—— 查询次数。接下来的 $q$ 行每行包含三个整数：$p_1$、$p_2$ 和 $len$（$0 \le p_1 \le |a| - len$；$0 \le p_2 \le |b| - len$），这些数字表示当前查询的参数。

Output q integers — the answers for the queries.

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