小天的贪吃蛇

题号：NC265359
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

现在有两条贪吃蛇，在一个 $n\times m$ 的矩阵中， $(1,1)$ 是左上角， $(n,m)$ 是右下角，蛇 $A$ 从 $(1,1)$ 开始，向右前进；蛇 $B$ 从 $(1,1)$ 开始，向下前进。路线如下图：

矩阵由小写字母构成，选定某个位置后，贪吃蛇从这个位置开始一直吃，直到遇到不一样的字符为止。

现在有 $q$ 次询问：
$1\ x\ y\ c$ ：将 $a_{x,y}$ 修改为 $c$ 。
$2\ x\ y$ ：蛇 $A$ 选择从 $(x,y)$ 开始吃。
$3\ x\ y$ ：蛇 $B$ 选择从 $(x,y)$ 开始吃。

对于每个询问 $2,3$ 输出贪吃蛇能吃的最多字符。

注意：贪吃蛇的路线是固定的，询问的只是开始吃时的位置。

输入描述:

第一行两个正整数 。

接下来  行，每行  个字符描述矩阵。第  行，第  列的字符表示 。

第  行一个正整数 。

接下来  行，每行描述一个操作：
：将  修改为 。
：蛇  选择从  开始吃。
：蛇  选择从  开始吃。

输出描述:

每行一个整数表示对于每个询问  输出贪吃蛇能吃的最多字符。

示例1

输入

复制

3 3
a b c
a a c
d e c
2
3 1 3
2 2 2

输出

复制

3
2