题目背景

翻译自 CSES-1652 题。

题目描述

给定一个 $n×n$ 的网格，表示一片森林的地图。每个格子要么是空的，要么包含一棵树。左上角的格子坐标为 $(1,1)$，右下角的格子坐标为 $(n,n)$。

你的任务是处理 $q$ 个查询，每个查询询问：给定一个矩形区域，区域内有多少棵树？

输入格式

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

接下来有 $n$ 行描述森林，每行包含 $n$ 个字符：. 表示空格，* 表示树。

最后有 $q$ 行，每行包含四个整数 $y_1,x_1,y_2,x_2$，表示一个矩形区域的两个对角线的坐标。

输出格式

对于每个查询，输出矩形区域内树的数量。

样例

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

3
1
2

说明/提示

$1 \leq n \leq 1000$；

$1 \leq q \leq 2 \cdot 10^5$；

$1 \leq y_1 \leq y_2 \leq n$；

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