题目内容

在一片矩形勘探区域中，共有 $n$ 行 $m$ 列单元格，每个单元格内标注了三种矿物代号之一：x、y、z。定义某个子矩形区域的矿物种类数为该区域内实际出现过的不同矿物代号数量。现在给出完整标注和 $q$ 次询问，每次询问指定一个子矩形，请回答该子矩形的矿物种类数。约束：矩阵的行数 n 和列数 m 均不超过 500；询问次数 q 不超过 50000；每次询问的左上角为第 $r_1$ 行第 $c_1$ 列，右下角为第 $r_2$ 行第 $c_2$ 列，满足 $1 \le r_1 \le r_2 \le n$ 且 $1 \le c_1 \le c_2 \le m$。

输入描述

第一行包含两个正整数 n 和 m，分别表示勘探区域的行数和列数。接下来 n 行，每行包含 m 个用空格分隔的字符，每个字符为 x、y 或 z，表示对应单元格的矿物代号。接下来一行包含一个正整数 q，表示询问次数。接下来 q 行，每行包含四个正整数 r1, c1, r2, c2，表示一次询问的子矩形左上角位置为第 r1 行第 c1 列，右下角位置为第 r2 行第 c2 列。

输出描述

输出 q 行，每行一个整数，表示对应子矩形内实际出现的不同矿物代号数量。

样例1