[yLOI2019] 棠梨煎雪

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

扶苏正在听《棠梨煎雪》的时候，@[spitfirekindergarten](https://www.luogu.org/space/show?uid=61795) 发来一道 [IOI2018 集训队作业题](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$ | $1$ | $0$ | $1$ | $5$ | | $2$ | $102$ | $102$ | $10$ | $10$ | | $3$ | $1003$ | $1003$ | $10$ | $15$ | | $4$ | $1004$ | $10004$ | $30$ | $15$ | | $5$ | $100005$ | $500005$ | $1$ | $15$ | | $6$ | $100006$ | $50006$ | $30$ | $10$ | | $7$ | $100007$ | $1000007$ | $30$ | $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