题目描述

给定一个 $n \times n$ 的方格图，代表一片森林的地图。地图中的每一个方格，要么是空地，要么长着一棵树。

这片森林的坐标系统定义如下：左上角的方格坐标为 $(1, 1)$，右下角的方格坐标为 $(n, n)$。

您的任务是处理 $q$ 个查询。每个查询会给定一个矩形的左上角和右下角坐标，您需要计算出这个矩形内共有多少棵树。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示森林的大小和查询的数量。

接下来 $n$ 行，每行包含 $n$ 个字符，描述了森林的地图。其中 . 代表空地，* 代表树。

最后有 $q$ 行，代表 $q$ 个查询。每行包含四个整数 $x_1, y_1, x_2, y_2$，表示一个查询矩形的左上角坐标 $(x_1, y_1)$ 和右下角坐标 $(x_2, y_2)$。

输出格式

对于每个查询，输出一行一个整数，代表对应矩形内树的数量。

4 3
.*..
*.**
**..
****
2 2 3 4
3 1 3 1
1 1 2 2

3
1
2

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 1000$，$1 \le q \le 2 \times 10^5$，$1 \le y_1 \le y_2 \le n$，$1 \le x_1 \le x_2 \le n$。