题目描述

你有一个 $n$ 行 $m$ 列的小写字母矩阵，你需要把这个矩阵切成两个连通的部分（分别至少一个字母），其中一部分的所有字母都小于另一部分的所有字母，求方案数。

但是这个问题太简单了，所以在此基础上有 $q$ 次操作，分为两种：

• $c\ x\ y$ 修改第 $x$ 行 $y$ 列的字符为 $c$，并求出当前的方案数。这个操作是临时的，也就是回答结束后操作就恢复。
• $\texttt{+}\ s$（$\texttt{+}$ 的 ASCII 为 $43$），新增一列，新列第 $x$ 行字符为 $s_x$，并求出当前的方案数。这个操作是永久的，会影响之后的询问。

输入格式

输入有三个正整数 $n,m,q$，分别表示行数、列数和询问数。

之后 $n$ 行，每行 $m$ 个字符，表示最开始的字符矩阵。

令 $ans_i$ 为第 $i$ 次操作之后的方案数。特别地，$ans_0$ 为初始方案数，$ans_{-1}=0$。

之后 $q$ 行，每行一个操作，为下面两种格式之一：

• $c\ x'\ y'$，表示一次修改操作，假如当前是第 $i$ 次操作，那么真实 $x=x'\oplus ans_{i-1}$，$y=y'\oplus ans_{i-2}$，其中 $\oplus$ 是按位异或。
• $\texttt{+}\ s$，表示一次增加操作。该操作不加密。

输出格式

输出 $ans_0,ans_1,\ldots, ans_q$，每个数一行。

样例 #1

样例输入 #1

3 3 6
aba
aee
eff
a 3 2
e 3 0
f 0 0
b 3 3
e 0 3
+ aaa

样例输出 #1

2
2
1
0
1
3
2

样例 #2, #3, #4, #5, #6

点我下载大样例

样例 $2\sim 6$ 分别满足测试点 $6,8,11,13,21$ 的限制。

提示

【样例解释】

一开始有如下两种划分方案（分为粗体和非粗体两块）：

方案 1	a	b	a	方案 2	a	b	a
	a	e			a	e
	e	f			e	f

第一次询问将第 $1$ 行第 $2$ 列修改成 a。

第二次询问将第 $1$ 行第 $2$ 列修改成 e。

第三次询问将第 $1$ 行第 $2$ 列修改成 f。

第四次询问将第 $3$ 行第 $2$ 列修改成 b。

第五次询问将第 $1$ 行第 $3$ 列修改成 e。

接下来新增一列，现在矩阵为：

abaa
aeea
effa

【数据范围】

Testcases	$n\le$	$m\le$	$q\le$	+ 数量 $\le$	特殊性质
$1$		$1000$	$5$	$0$
$2$	$2$
$3$				$2$
$4$	$4$	$4$		$0$
$5$		$3$		$2$
$6,7$	$400$	$1000$		$0$	字符只有 a,b
$8,9,10$
$11,12$			$10^5$		输入矩阵第奇数列等于后一列
$13,14$					询问点左侧和上方字符相同
$15\sim 18$
$19,20$				$1000$	询问点左侧和上方字符相同
$21\sim25$

对于全体数据，保证 $1\le n\le 400$，$1\le m\le 1000$，$1\le q\le 10^5$，其中加列不超过 $1000$ 次，所有字符串都只有小写字母。