#CS1652. 森林查询 I

森林查询 I

题目背景

翻译自 CSES-1652 题。

题目描述

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

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

输入格式

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

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

最后有 q 行，每行包含四个整数 y1,x1,y2,x2y_1,x_1,y_2,x_2y1​,x1​,y2​,x2​，表示一个矩形区域的两个对角线的坐标。

输出格式

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

样例

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

3
1
2

说明/提示

$1 \leq n \leq 10$

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

1≤y1≤y2≤n1 \leq y_1 \leq y_2 \leq n1≤y1​≤y2​≤n；

1≤x1≤x2≤n1 \leq x_1 \leq x_2 \leq n1≤x1​≤x2​≤n。