P12009 【MX-X10-T5】[LSOT-4] Masuko or Haru？

Shion 作为社团活动后的作业，给 Yotsuba 出了一道数据结构题。 Yotsuba 本来是想用水路查资料的，但是查着查着就去和 Haru 聊天了…… 但是还有 1 秒就要到下午 5 点了！Yotsuba 只能去询问 Masuko 这道题怎么做了。 Masuko 当然可以在 1 秒之内解决这道题，她现在想考考你看你能不能 1 秒内解决这道题！

给你 $n$ 个长度为 $m$ 的 01 串。 区间二元组的定义为满足 $1\le l\le r\le m$ 的二元组 $(l,r)$。 区间集合的定义为区间二元组组成的集合。 定义 01 串 $a$ 关于区间集合 $S$ 的一次变化为任选一个区间二元组 $(l,r)\in S$，$\forall i\in[l,r],a_i\gets a_i\oplus 1$（$\oplus$ 代表二进制按位异或）。 定义 01 串 $a$ 和 $b$ 在区间集合 $S$ 下等价为 $a$ 可以在经过任意次关于 $S$ 的变化后变为 $b$。 刚开始时 $S=\emptyset$。 一共有 $q$ 次操作，每次操作都为插入操作或询问操作。 插入操作为给定一个区间二元组 $(l,r)$，$S\gets S\cup \{(l,r)\}$。 询问操作为给定 $x,y$，你需要判断第 $x$ 个 01 串和第 $y$ 个 01 串是否关于区间集合 $S$ 等价。

无

无

**【样例解释 #1】** 每个 01 串初始形如： `10011`， `11001`。 - 第一次询问：此时集合 $S$ 为空。两个 01 串显然不同。 - 第二次询问：此时集合 $S$ 为 $\{(2,3)\}$，则第一个串只能变成 `10011` 或 `11111`，无法变得相同，故不等价。 - 第三次询问：此时集合 $S$ 为 $\{(2,3),(3,4)\}$，依次进行 $(2,3)$ 变换和 $(3,4)$ 变换即可变为第二个串。故等价。 **【数据范围】** **本题采用捆绑测试。** - 子任务 1（17 分）：$n,m\le 10$，$q\le 20$。 - 子任务 2（14 分）：$l=r$。 - 子任务 3（16 分）：$l=r-1$。 - 子任务 4（13 分）：插入操作不超过 $5000$ 次。 - 子任务 5（21 分）：所有的插入操作在所有的询问操作之前。 - 子任务 6（19 分）：无特殊性质。 对于全部的数据，$1\le q,n,m\le 5\times 10^6$，$n\times m\le 10^7$，$1\le l\le r\le m$，$1\le x,y\le n$，$op\in\{1,2\}$。