#P1505. 2023.08.27-ZJTD秋招第二场-第二题-矩阵查询

2023.08.27-ZJTD秋招第二场-第二题-矩阵查询

题目描述

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

输入描述

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

接下来的nn行,每行输入mm个字符串ss (s{x,y,z}s \in \{x,y,z\} )

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

接下来的qq行,每行输入四个正整数x1,y1,x2,y2x_1,y_1,x_2,y_2,代表询问的子矩阵左上角为第x1x_1行第y1y_1列,右下角为第x2x_2行第y2y_2列。

1n,m5001 \leq n,m \leq 500

1q500001 \leq q \leq 50000

1x1x2n1 \leq x_1 \leq x_2 \leq n

1y1y2m1 \leq y_1 \leq y_2 \leq m

输出描述

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

样例

输入

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

输出

1
3