题目描述

有两个 01 串 $S$ 和 $T$，长度分别为 $n$ 和 $m$。

有 $q$ 次询问，每次询问给出四个正整数 $l_1, r_1, l_2, r_2$，保证 $l_1 \le r_1, l_2 \le r_2$ 且 $r_1 - l_1 + 1 = r_2 - l_2 + 1$。

设满足 $1 \le i \le r_1 - l_1 + 1$ 且 $S_{l_1 + i - 1} \ne T_{l_2 + i - 1}$ 的 $i$ 的数量为 $p$。请你求出 $p$ 对 $2$ 取模后的值。

输入格式

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

第 $2$ 行一个长为 $n$ 的字符串，表示 $S$。

第 $3$ 行一个长为 $m$ 的字符串，表示 $T$。

第 $4$ 行一个正整数 $q$，表示询问次数。

接下来 $q$ 行，每行四个正整数 $l_1, r_1, l_2, r_2$，含义如题所示。

输出格式

一行，一个正整数，表示 $p$ 对 $2$ 取模后的值。

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

说明/提示

【数据范围】

对于 $30\%$ 的测试数据，$n, m, q \le 5000$。

对于 $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$。