题目背景

岁岁花藻檐下共将棠梨煎雪，
自总角至你我某日辗转天边。
天淡天青，宿雨沾襟，
一年一会信笺却只见寥寥数言。

——银临《棠梨煎雪》

题目描述

扶苏正在听《棠梨煎雪》的时候，

训队作业题](http://uoj.ac/problem/425)：我切了这集训队题，辣鸡扶苏快过来做题。扶苏定睛一看，这不 s* 题嘛，写了一发交上去才发现自己看错题目了。但是写完的代码不能浪费，于是就有了这道题。

歌词中的主人公与她的朋友一年会有一次互相写信给对方，一共通信了 $m$ 年。为了简化问题，我们认为她们每封信的内容都是一条二进制码，并且所有二进制码的长度都是 $n$。即每封信的内容都是一个长度为 $n$ 的字符串，这个字符串只含字符 0 或 1。

这天她拿出了朋友写给她的所有信件，其中第 $i$ 年的写的信件编号为 $i$。由于信件保存时间过久，上面有一些字符已经模糊不清，我们将这样的位置记为 ?，? 字符可以被解释为 0 或 1。由于她的朋友也是人，符合人类的本质，所以朋友在一段连续的时间中书写的内容可能是相同的。现在她想问问你，对于一段连续的年份区间 $[l,r]$ 中的所有信件，假如朋友在这段时间展示了人类的本质，所写的是同一句话，那么这一句话一共有多少种可能的组成。也即一共有多少字符串 $S$，满足在这个区间内的所有信件的内容都可能是 $S$。

一个长度为 $n$ 的只含 0,1,? 的字符串 $A$ 可能是一个字符串 $B$ 当且仅当 $B$ 满足如下条件：

• $B$ 的长度也是 $n$ 。
• $B$ 中只含字符 0,1。
• $A$ 中所有为 0 的位置在 $B$ 中也是 0。
• $A$ 中所有为 1 的位置在 $B$ 中也是 1。
• $A$ 中为 ? 的位置在 $B$ 中可以为 0 也可以是 1。

同时她可能会突然发现看错了某年的信的内容，于是她可能会把某一年的信的内容修改为一个别的只含 0,1,? 的长度为 $n$ 的字符串。

输入格式

每个输入文件中都有且仅有一组测试数据。

输入数据第一行为三个用空格隔开的整数，分别代表代表字符串长度 $n$，字符串个数 $m$ 和操作次数 $q$。

下面 $m$ 行，每行是一个长度为 $n$ 的字符串，第 $(i + 1)$ 行的字符串 $s_i$ 代表第 $i$ 年信的内容。

下面 $q$ 行，每行的第一个数字是操作编号 $opt$。

• 如果 $opt=0$，那么后面接两个整数 $[l,~r]$，代表一次查询操作。
• 如果 $opt=1$，那么后面接一个整数 $pos$，在一个空格后会有一个长度为 $n$ 的字符串 $t$，代表将第 $pos$ 个字符串修改为新的字符串 $t$。

输出格式

为了避免输出过大，请你输出一行一个数代表所有查询的答案异或和对 $0$ 取异或的结果。

3 3 5
010
0?0
1?0
0 1 2
0 2 3
1 3 0??
0 2 3
0 1 3

2

提示

样例 1 解释

• 对于第一次询问，只有串 010 符合要求。
• 对于第二次询问，由于第二个串的第一位为 1，第三个串的第一位为 0，故没有串符合要求。
• 修改后将第三个串修改为 0??。
• 对于第四次询问，有两个串符合要求，分别为 000 和 010。
• 对于第五次询问，只有 010 符合要求。

故答案为 $1,0,2,1$，他们的异或和再异或 $0$ 的值为 $2$。

---

数据规模与约定

本题采用多测试点捆绑测试，共有 7 个子任务。

子任务编号	$m =$	$q =$	$n =$	子任务分数
$1$		$0$	$1$	$5$
$2$	$102$		$10$	$10$
$3$	$1003$			$15$
$4$	$1004$	$10004$	$30$
$5$	$100005$	$500005$	$1$
$6$	$100006$	$50006$	$30$	$10$
$7$	$100007$	$1000007$		$30$

对于全部的测试点，保证：

• $1 \leq m \leq 10^5 + 7$，$0 \leq q \leq 10^6 + 7$，$1 \leq n \leq 30$。
• $0 \leq opt \leq 1$，$1 \leq pos \leq m$，$1 \leq l \leq r \leq m$。
• $s_i, t$ 的长度均为 $n$ 且只含有字符 0,1,?。
• 输入字符串的总长度不超过 $5 \times 10^6$。数据在 Linux 下生成，即换行符不含 \r。

---

提示

• 请注意常数因子对程序效率造成的影响。
• 请注意数据读入对程序效率造成的影响。
• 请注意输入的问号为嘤文问号，即其 ASCII 值为 $63$

注: 为减少错误做法的通过率，时限于 2020 年 7 月由 2000ms 改为 1500ms