You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个字符串矩阵，字符串只含$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