问题描述

给出两个长度为 $n$ 的01序列A、B，有Q次询问，每次询问当把A的第i位和B的第j位对齐时，A,B公共部分有多少对对齐且相同的数。

输入格式

第一行，两个整数 $N,M$ 。

第二行，一个长度为$N$的字符串，只包含'0'和'1'两种字符，代表A序列。

第三行，一个长度为$M$的字符串，只包含'0'和'1'两种字符，代表B序列。

第四行，一个整数$Q$。

接下来Q行，每行两个整数$i,j$。

输出格式

输出$Q$行，每行表示每次询问的答案。

样例输入

6 6

000111

111100

3

1 1

1 2

4 2

样例输出

1

0

3

提示

数据范围：

1<=$N$,$M$<=100000

1<=$Q$<=1000000