P14925 [北大集训 2025] 异形工厂

在异形工厂里，有一种叫“轮换器”的工具。使用一次轮换器可以将一个 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$。

### 【样例 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$。 | 子任务编号 | 分值 | $n, q \le$ | 特殊性质 | |:-:|:-:|:-:|:-:| | 1 | 10 | $10$ | 无 | | 2 | 10 | $2 \times 10^3$ | A | | 3 | 25 | $2 \times 10^3$ | 无 | | 4 | 20 | $2 \times 10^5$ | 无 | | 5 | 10 | $5 \times 10^5$ | A | | 6 | 25 | $5 \times 10^5$ | 无 | 特殊性质 A：对于所有 $1 \le i \le \lfloor \frac{n+1}{2} \rfloor$，均有 $s_{2i-1} = t_{2i-1} = 0$。