题目描述

在异形工厂里，有一种叫“轮换器”的工具。使用一次轮换器可以将一个 01 串中长度恰好为 $3$ 的子串循环移位，即将 $xyz$ 替换为 $yzx$ 或 $zxy$。

给定长度为 $n$ 的 01 串 $s, t$。有 $q$ 次询问，每次询问会给定 $l, r$，求最少需要使用多少次轮换器才能将 $s[l,r]$ 变为 $t[l,r]$。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, q$，分别表示字符串 $s, t$ 的长度和询问次数。

输入的第二行包含一个长度为 $n$ 的 01 字符串 $s$。

输入的第三行包含一个长度为 $n$ 的 01 字符串 $t$。

输入的第 $i+3$ ($1 \le i \le q$) 行包括两个正整数 $l, r$，表示第 $i$ 次询问。

输出格式

输出到标准输出。

对于每次询问，输出一行一个整数表示使用轮换器的最少次数。特别地，若无论如何都无法将 $s[l,r]$ 变为 $t[l,r]$，则输出 $-1$。

10 5
1010111000
1111000001
1 6
3 5
4 5
1 10
8 9

3
1
-1
5
0

提示

【样例 1 解释】

对于第一次询问，一种可能的操作方式为：

1. 选择子串 $[4,6]$，将 $011$ 替换为 $110$，得到 $101110$；
2. 选择子串 $[2,4]$，将 $011$ 替换为 $110$，得到 $111010$；
3. 选择子串 $[4,6]$，将 $010$ 替换为 $100$，得到 $111100$。

【子任务】

对于所有测试数据，均有：

• $1 \le n, q \le 5 \times 10^5$；
• 对于所有 $1 \le i \le n$，均有 $s_i, t_i \in \{0,1\}$；
• $1 \le l \le r \le n$。

特殊性质 A：对于所有 $1 \le i \le \lfloor \frac{n+1}{2} \rfloor$，均有 $s_{2i-1} = t_{2i-1} = 0$。