题目描述

给定一个字符串矩阵，字符串只含$x,y,z$ , 处理$q$次询问，每次询问一个子矩阵，输出这个子矩阵的本质不同字符串个数。

输入描述

第一行输入两个正整数$n,m$，代表矩阵的行数和列数

接下来的$n$行，每行输入$m$个字符串$s$ ($s \in \{x,y,z\}$ )

接下来的一行，输入一个正整数$q$，代表询问次数。

接下来的$q$行，每行输入四个正整数$x_1,y_1,x_2,y_2$，代表询问的子矩阵左上角为第$x_1$行第$y_1$列，右下角为第$x_2$行第$y_2$列。

$1 \leq n,m \leq 500$

$1 \leq q \leq 50000$

$1 \leq x_1 \leq x_2 \leq n$

$1 \leq y_1 \leq y_2 \leq m$

输出描述

输出$q$行，每行输出一个整数，代表子矩阵的本质不同字符串个数。

样例

输入

3 3
x y y
x y y
z z z
2
1 2 2 3
2 1 3 2

输出

1
3

思路:二维前缀和模板题

问题化简：给定一个矩阵，每次询问一个子矩阵中不同种类的字符串。

关键：字符串种类非常少，只有三种。所以我们暴力的开三个二维数组。每个二维数组用来记录一种字符串的二维前缀和。然后查询的时候分三次查询即可。

问题：二维前缀和是啥？？

跟着塔子哥入门就完事了：前缀和入门+练习