Check Answer S

题目描述

\(LP\) 正在参加一场历史测试，然而他并不会大多数题目。

现在教室里有 \(N\) 个学生。 历史测验有 \(M\) 道选择题。 选择题只有\(A,B,C,D\) 四个选项 , 且只有单选。

为了让自己AK , \(LP\) 会使用"千里眼"技能 , 让他可以看见学号在 \([l,r]\) 区间内的同学的答案。

有的同学可能不会某一道题，填涂了空白。 当然，他后面可能会改动答案。

他想知道存在多少种答案，使得在学号在区间 \([l,r]\) 内的同学已经填涂的答案与这份答案完全相符。

输入格式

第一行三个整数\(N,M,Q\) , 表示学生数，题目数量，查询数。

其后 \(N\) 个长度为 \(M\) 的字符串，由 ABCD? 字符组成，表示填涂了\(A,B,C,D\)或未填涂。

其后 \(Q\) 行，一行三个参数 \(opt , u , v\) ， 表示：

• \(opt = 0\) ， 表示 \(u\) 号同学的答案改为 \(v\) 。
• \(opt = 1\) ， 表示 \(LP\) 想知道存在多少种答案，使得在学号在区间 \([u,v]\) 内的同学已经填涂的答案与这份答案完全相符。

输出格式

对于每一个 \(opt = 1\) , 输出一行所求答案。

输入输出样例 #1

输入 #1

3 3 5
AB?
?B?
C?B
1 1 2
1 2 3
1 1 3
0 1 ???
1 1 3

输出 #1

4
1
0
1

说明/提示

样例解释1

对于查询 \(1\) : 有 \(4\) 种答案满足要求 ， 分别是 ABA , ABB , ABC , ABD 。

对于查询 \(2\) : 有 \(1\) 种答案满足要求 ， 这个答案是是 CBB 。

对于查询 \(3\) : 没有任何答案满足要求。

改动后， 原答案元组变为 \(???, ?B?, C?B\)

对于查询 \(5\) : 有 \(1\) 种答案满足要求 ， 这个答案是 CBB 。

对于\(100\%\) 的数据： \(N \le 10^5 , M \le 30 , Q \le 10^5\)