题目描述

你有两个长度分别为 $n,m$ 的 $01$ 串 $S,T$。

有 $Q$ 次询问，每次询问给出 $l_1,r_1,l_2,r_2$，其中 $r_1-l_1+1=r_2-l_2+1$，令 $a=S[l_1\ldots r_1]$，$b=T[l_2\ldots r_2]$，你需要求出 $a_i\not=b_i$ 的位置个数对 $2$ 取模的值。

输入格式

第一行两个正整数 $n,m$，分别表示 $S,T$ 的长度。

接下来两行输入两个 $01$ 串表示 $S$ 和 $T$。

接下来一行一个整数 $Q$，表示询问的个数。

接下来 $Q$ 行，每行四个整数 $l_1,r_1,l_2,r_2$，表示一组询问。

输出格式

对于每组询问，输出一个数 $0$ 或 $1$ 表示答案。

样例

7 3
1011100
010
4
4 5 2 3
4 4 2 2
5 6 2 3
5 6 1 2

1
0
0
0

另有一组大样例，见附加文件中的的 string/string2.in 和 string/string2.ans。

数据范围

• 对于 $30\%$ 的数据，$n,m,q\le 5\times 10^3$；
• 对于 $70\%$ 的数据，$n,m,q\le 5\times 10^4$；
• 对于 $80\%$ 的数据，$n,m,q\le 10^5$；
• 对于 $100\%$ 的数据，$1\le n,m,q\le 2\times 10^5$，$1\le l_1\le r_1\le n$，$1\le l_2\le r_2\le m$；