#WW008D. 真的是毒瘤题吗?

真的是毒瘤题吗?

题目描述

同学们常常说TooY0ung是毒瘤出题人 良心出题人,TooY0ung可以负责任的说,今天的题真的不毒瘤。

你有一个矩阵(没学过矩阵概念的同学,其实理解为二维数组就好了),矩阵上每个格子都有一个小写字母。

请你维护以下两种操作:

  • 输入 1 x y c,将第xx行第yy列的字母修改为cc
  • 输入 2 s,查询ss单词在矩阵中出现的次数。

ss的长度不超过44

注:我们定义,单词在矩阵中出现当且仅当向下、向右、向右下 (和水平线夹角 135度)三种方向即可,且必须是一条直线上的字符 (不能转弯)。具体可以参考样例说明。

输入格式

第一行输入两个正整数 n,mn,m ,用空格隔开,代表矩阵的行数和列数。

接下来的nn行,每行输入一个长度为 mm 的字符串,代表字符矩阵

接下来的一行输入一个正整数 qq ,代表操作次数。

接下来的 qq 行,每行输入一行操作,操作如题意所示

输出格式

对于每次 22 号操作,输出一个整数代表答案。

3 4
abcd
cbae
cccc
3
2 abc
1 3 3 b
2 ab
2
3

提示

image

数据规模与约定

对于 100%100\% 的数据 保证 1n,m3001 \leq n,m \leq 300 , 1q1051 \leq q \leq 10^5

子任务划分:

  • 子任务 1(30 分):保证 1n,m101 \leq n,m \leq 10 , 1q1001 \leq q \leq 100,且只有操作 2
  • 子任务 2(30 分):保证 1n,m101 \leq n,m \leq 10 , 1q1001 \leq q \leq 100
  • 子任务 3(40 分):没有特殊限制