[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$ 取异或的结果。

输入输出样例

输入样例 #1

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

输出样例 #1

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