题目描述

给你 $n$ 个长度为 $m$ 的 01 串以及一个区间集合 $S$，初始时 $S$ 为空。

定义对一个 01 串的一次操作为在 $S$ 里找到一个区间 $[l,r]$ 并将这个 01 串的第 $l$ 到 $r$ 个数反转，$0$ 变 $1$，$1$ 变 $0$。

定义两个 01 串是本质相同的当且仅当可以通过若干次操作将一个 01 串变成另一个 01 串。

给出 $q$ 次询问。

1. 插入：向 $S$ 内新增一个区间 $[l,r]$。
2. 询问：询问第 $x$ 个与第 $y$ 个 01 串是否本质相同。

输入格式

第一行，三个整数 $n,m,q$。

接下来 $n$ 行，每行一个长为 $m$ 的 01 串，表示第 $i$ 个 01 串。

接下来 $q$ 行，每行三个正整数，第一个正整数为 $op$。

• 如果 $op=1$ 代表为插入，接下来两个正整数 $l,r$。
• 如果 $op=2$ 代表为询问，接下来两个正整数 $x,y$。

输出格式

输出一行一个字符串，对于每组询问，依次输出一个字符，如果本质相同则输出1，否则输出0。

输入输出样例 #1

输入 #1

2 5 5
10011
11001
2 1 2
1 2 3
2 1 2
1 3 4
2 1 2

输出 #1

001

样例解释 #1

• 第一次询问：此时集合 $S$ 为空。两个 01 串显然不同。
• 第二次询问：此时集合 $S$ 为 $\{[2,3]\}$，则第一个串只能变成 10011 或 11111，无法变得相同，故本质不相同。
• 第三次询问：此时集合 $S$ 为 $\{[2,3],[3,4]\}$，依次进行 $[2,3]$ 变换和 $[3,4]$ 变换即可变为第二个串，故本质相同。

说明 / 提示

本题开启捆绑测试点与子任务依赖。

对于全部数据，$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\}$，输入皆为整数。